[PS] 백준 9465 스티커

문제

BJ 9465 스티커
문제 분류 : DP
문제 난이도 : 실버1

문제 코드

import sys
from collections import deque
import itertools
import heapq

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

k = int(input())
ans = []

for kk in range(k):
    n = int(input())
    g = [list(map(int, input().split())) for _ in range(2)]
    dp = [item[:] for item in g]

    if n != 1:

        dp[0][1] += g[1][0]
        dp[1][1] += g[0][0]

        for i in range(2, n):
            dp[0][i] += max(dp[1][i-2], dp[1][i-1])
            dp[1][i] += max(dp[0][i-2], dp[0][i-1])

    ans.append(max(dp[0][n-1],dp[1][n-1]))

print(*ans, sep = '\n')

문제 복기 & 느낀점

메모이제이션 배열을 적절하게 이용하는 전형적인 DP 문제.

이전에 풀어봤던 문제처럼 적절하게 case를 나눠서 특정 시점까지의 최대값을 저장하는 형식이다. 분명 이전까지의 문제들과 비슷하게 해결할 수 있다고 생각해서 점화식을 유도하려고 이것저것 해봤지만 생각해내지 못했다ㅠㅠ.

결국 문제의 제약 사항을 어기지 않으면서 특정 시점까지의 최대값을 유기적으로 도출해 낼 수 있는 감각이 중요한 것 같다.