이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 스티커를 붙일 수 있는 여부의 패턴을 보면 현재 스티커와 대각선의 위치, 그리고 대각선의 옆 위치에 있는 스티커를 같이 붙일 수 있다. 이를 이용하여 dp리스트를 2차원 리스트로 선언하고, 윗줄 스티커는 아래쪽 대각선과 대각선 옆에 위치한 스티커 중 더 큰 스티커를 선택하도록 하고, 아랫줄 스티커는 윗쪽 대각선과 대각선 옆에 위치한 스티커 중 더 큰 스티커를 선택하도록 하여 윗줄과 아랫줄의 값 중 가장 큰 값을 출력하도록 하였다. 점화식은 다음과 같다.

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

Code

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