백준 9465 스티커 Python

https://www.acmicpc.net/problem/9465
전형적인 dp 문제 

9465번: 스티커

비슷한 문제를 이전에 풀어서 쉽게 풀 수 있었다 

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

1309번: 동물원

다만 1309번은 경우의 수만 세어주면 되는데, 9465번은 스티커의 값을 누적해서 합해야 한다는 것이 다르다. 

import sys 
input = sys.stdin.readline 
t = int(input())
for _ in range(t):
    n = int(input()) # 열의 길이
    array = []
    dp = [[0, 0, 0] for _ in range(n+1)]
    for i in range(2):
        array.append(list(map(int, input().split())))

    for i in range(1,n+1):
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) # 이번 칸에서 아무것도 선택 안하는 경우
        # 1열 스티커 선택 + 이전에 2열스티커 or 1열 스티커 선택 + 이전에 아무것도 선택x
        dp[i][1] = max(array[0][i-1] + dp[i-1][2], array[0][i-1] + dp[i-1][0])
        # 2열 스티커 선택 + 이전에 1열스티커 or 2열 스티커 선택 + 이전에 아무것도 선택x
        dp[i][2] = max(array[1][i-1] + dp[i-1][1], array[1][i-1] + dp[i-1][0])

    print(max(dp[n]))