백준 9465 [스티커] 파이썬

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

9465번: 스티커

import sys
input = sys.stdin.readline
N = int(input())

for _ in range(N):
    n = int(input())
    lineO = list(map(int, input().split()))
    lineT = list(map(int, input().split()))
    dp = [[0]*(n) for _ in range(2)]
    dp[0][0] = lineO[0]
    dp[1][0] = lineT[0]
    if n > 1:
        dp[0][1] = max(lineO[1]+lineT[0],lineO[0])
        dp[1][1] = max(lineT[1]+lineO[0],lineT[0])
        for i in range(2, n):
            dp[0][i] = max(dp[0][i-2]+lineT[i-1]+lineO[i],
                           dp[1][i-2]+lineO[i], dp[0][i-1])
            dp[1][i] = max(dp[1][i-2]+lineO[i-1]+lineT[i],
                           dp[0][i-2]+lineT[i], dp[1][i-1])
    print(max(max(dp[0]), max(dp[1])))

각 열별로 최적의 해를 찾는다.