문제링크

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

풀이

입력과 똑같은 사이즈의 DP테이블을 만들었다.
DP의 각 항은 해당 위치의 스티커를 선택했을 때 가질 수 있는 점수의 최댓값이다.
특정 위치를 선택하면 그 위치의 상하좌우를 모두 쓸 수 없으므로 DP값을 정할 때 그림과 같은 위치의 항들의 최댓값을 더해주었다.

DP[0][n-1]을 정할 때는 DP[1][n-2]와 DP[1][n-3]을 써준다. DP[0][n-3]의 값을 포함한다면 list[1][n-2] 위치의 스티커 점수가 손실이 되기 때문에 참고하지 않는다.

위 원리를 적용하기 위해서는 0,1번째의 DP를 초기화시켜야하므로 n이 1인 경우는 따로 빼줬다.

import sys
t=int(input())
for _ in range(t):
    n=int(input())
    l=[list(map(int,sys.stdin.readline().split(" "))) for __ in range(2)]
    if n==1:
        print(max(l[0][0],l[1][0]))
        continue
    dp=[[0]*n for __ in range(2)]
    dp[0][0]=l[0][0]
    dp[1][0]=l[1][0]
    dp[0][1]=l[1][0]+l[0][1]
    dp[1][1]=l[0][0]+l[1][1]
    for i in range(2,n):
        dp[0][i]=l[0][i]+max(dp[1][i-1],dp[1][i-2])
        dp[1][i]=l[1][i]+max(dp[0][i-1],dp[0][i-2])
    print(max(dp[0][n-1],dp[1][n-1]))