[Python] 백준 9465번 - 스티커

# 9465
import sys

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    top = list(map(int, sys.stdin.readline().split()))
    top.insert(0, 0)
    bottom = list(map(int, sys.stdin.readline().split()))
    bottom.insert(0, 0)
    arr = [top, bottom]

    for column in range(2, n + 1):
        for row in range(2):
            if row == 0:
                arr[row][column] += max(arr[row + 1][column - 1], arr[row + 1][column - 2])
            else:
                arr[row][column] += max(arr[row - 1][column - 1], arr[row - 1][column - 2])
            # print(f"row:{row}, column:{column}")
            # print(f"{arr[row][column]}")

    print(max(arr[0][n], arr[1][n]))

DP로 푸는 문제였다. 

 

이동할 수 있는 경우의 수를 아래->위 2가지, 위-> 아래 2가지로 나누는게 포인트 였다.