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

이런 DP 비슷한 문제들은 아직 어색해서 푸는데 오래 걸렸다.

변을 공유하는 현재 스티커를 고른다면 위 혹은 밑, 양옆의 스티커는 포기해야 하는데,

이전 대각선과 전전 대각선의 값을 현재 값과 각각 더해 비교하여 큰 값을 취하는 방식으로 문제를 풀었다.

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