[다이나믹 프로그래밍] 백준 9465번: 스티커 / 실버 1

https://www.acmicpc.net/problem/9465

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

probs = int(input())
for _ in range(probs):
    n = int(input())
    up = list(map(int, input().split()))
    down = list(map(int, input().split()))

    dp1 = [0 for _ in range(n)]
    dp2 = [0 for _ in range(n)]
    
    dp1[0]= up[0]
    dp2[0]= down[0]
    
    if n == 1:
        print(max(dp1[0], dp2[0]))
        continue
        
    dp1[1] = dp2[0] + up[1]
    dp2[1] = dp1[0] + down[1]
    for i in range(2, n):
        dp1[i] = up[i] + max(dp2[i-1], dp2[i-2])
        dp2[i] = down[i] + max(dp1[i-1], dp1[i-2]) 

    print(max(dp1[-1],dp2[-1]))

dp는 오랜만에 보면 체감난이도가 매우 높다.

경험상 현시점 이전까지는 이미 최적 값이 계산되었다고 가정하고

이전 스텝과의 연관 관계를 살펴보는 것이 쉽게 가는 방법인 것 같다.