[백준/BOJ] - 9465번 python 풀이 - dp

---

1. 동서남북 스티커는 고를 수 없다.

2. 열이 0인 dp는 arr값과 동일하다.

3. 빨간 동그라미를 기준으로 하면 파란 동그라미들의 dp값 중 큰 값을 기준으로 20의 dp값을 갱신한다.

 

 

---

정답

import sys
input = sys.stdin.readline
maxi = 0
n = int(input())
for _ in range(n):
    m = int(input())
    arr = []
    for i in range(2):
        arr.append(list(map(int,input().split())))
    dp = [[0 for _ in range(m)] for _ in range(2)]
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]
    for j in range(1,m):
        if j == 1:
            dp[0][j] = dp[1][j-1] + arr[0][j]
            dp[1][j] = dp[0][j-1] + arr[1][j]
        else:
            dp[0][j] = max(dp[1][j-1],dp[1][j-2]) + arr[0][j]
            dp[1][j] = max(dp[0][j-1],dp[0][j-2]) + arr[1][j]
    print(max(map(max,dp)))