[알고리즘/백준] 9465: 스티커(python)

0 1 2 3 4
50 40
30 100

1번 인덱스는 왼쪽 대각선의 수를 더해준다.

그 다음 인덱스 부터는 왼쪽 대각선의 두개의 수 중에 더 큰 수를 더해준다.

dp[0][i] = max(dp[1][i-1], dp[1][i-2])
dp[1][i] = max(dp[0][i-1], dp[0][i-2])

for _ in range(int(input())):
    N = int(input())
    dp = [list(map(int, input().split()))for _ in range(2)]
    for i in range(1, N):
        if i == 1:
            dp[0][i] += dp[1][i-1]
            dp[1][i] += dp[0][i-1]
        else:
            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]))