백준 알고리즘 9465번 스티커(python)

기본적인 다이나믹 프로그래밍 문제이다. 뒤쪽 대각선 방향으로 첫 번째, 두 번째 위치의 값 중 큰 걸 선택하면 된다.

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

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

for _ in range(int(input())):
    n = int(input())
    dp = [[0]+list(map(int, input().split())) for _ in range(2)]    
    for j in range(2, n+1):
        dp[0][j] += max(dp[1][j-1], dp[1][j-2])
        dp[1][j] += max(dp[0][j-1], dp[0][j-2])
    print(max(dp[0][n], dp[1][n]))