[백준/9465/파이썬] 스티커 - DP

---

소스코드

T = int(input())
def sticky(sticker, dp):
    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    if n == 1:
        return max(dp[0][0], dp[1][0])
    dp[0][1] = sticker[0][1] + sticker[1][0]
    dp[1][1] = sticker[1][1] + sticker[0][0]
    if n == 2:
        return max(dp[0][1], dp[1][1])
    for i in range (2,n):
        dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + sticker[0][i]
        dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + sticker[1][i]
    return max(dp[0][-1], dp[1][-1])

for _ in range(T):
    n = int(input())
    dp = [[0] * n for _ in range (2)]
    sticker = [list(map(int, input().split())) for _ in range(2)]
    print(sticky(sticker,dp))

---

알고리즘

이번 문제에서 생각했어야 하는 점은 2가지가 있는데

1. dp를 2차원으로 나눠야 했다는 것

2. 대각선으로 쭉 더해온 case와 이전까지 더해온 숫자들에서 한칸 띄고 새로 시작하는 case이다.