Search

[백준 9465] 스티커

[백준 9465] 스티커

Tip

점화식
dp[0][i] += max(dp[1][i - 1], dp[1][i - 2])
dp[1][i] += max(dp[0][i - 1], dp[0][i - 2])
max() 함수를 사용하여 둘 중 큰 값을 선택
런타임 에러 (IndexErr)의 경우
n이 1과 2 조건일 때 따로 처리

풀이 소스 코드

import sys si = sys.stdin.readline t = int(si()) for _ in range(t): n = int(si()) d = [list(map(int, si().split())) for _ in range(2)] if n == 1: print(max(d[0][0], d[1][0])) elif n == 2: print(max(d[0][0] + d[1][1], d[1][0] + d[0][1])) else: d[0][1] += d[1][0] d[1][1] += d[0][0] for i in range(2, n): d[0][i] += max(d[1][i - 1], d[1][i - 2]) d[1][i] += max(d[0][i - 1], d[0][i - 2]) print(max(d[0][n - 1], d[1][n - 1]))
Python