[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를 나눠서 특정 시점까지의 최대값을 저장하는 형식이다. 분명 이전까지의 문제들과 비슷하게 해결할 수 있다고 생각해서 점화식을 유도하려고 이것저것 해봤지만 생각해내지 못했다ㅠㅠ.
결국 문제의 제약 사항을 어기지 않으면서 특정 시점까지의 최대값을 유기적으로 도출해 낼 수 있는 감각이 중요한 것 같다.
Author And Source
이 문제에 관하여([PS] 백준 9465 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsb100800/PS-백준-9465-스티커저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)