[백준] 9465번: 스티커 (Python, 파이썬)

문제 링크: https://www.acmicpc.net/problem/9465

9465번: 스티커

 

파란색: dp[0][0]에서 시작하는 경우
빨간색: dp[1][0]에서 시작하는 경우

Key point
dp += max(대각선에서 왔을 때, 한 칸 전의 대각선에서 왔을 때)
마지막엔 dp[0][n-1]의 값과 dp[1][n-1]의 값 중 큰 값으로 골라주면 된다.

T = int(input())

for _ in range(T):
    n = int(input())
    dp = []
    for _ in range(2):
        dp.append(list(map(int, input().split())))

    if n == 1:
        print(*max(dp))
    
    elif n > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

        for i in range(2, n):
            dp[0][i] += max(dp[1][i-1], dp[1][i-2])
            dp[1][i] += max(dp[0][i-1], dp[0][i-2])

        print(max(dp[0][n-1], dp[1][n-1]))