[백준] 11052번: 카드 구매하기(python)

📌 문제

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

🗒 풀이

import sys


input = sys.stdin.readline

N = int(input())
price = [0] + list(map(int, input().split()))

dp = [0] * (N + 1)  # [0 for _ in range(N + 1)]

for i in range(1, N+1):
    for j in range(1, i + 1):
        dp[i] = max(dp[i], (price[j] + dp[i - j]))

print(dp[N])

뭔가 규칙도 보이고, 이런 식으로 접근하면 될 거란 생각은 들었는데, 저 한 줄이 잘 써지지가 않아서 고민했다.

일단 앞서 1463번 문제처럼 사람이 판단하기에 좀 더 낫게끔 dp와 price 각각 인덱스 0을 추가해준다.

 

우리가 원하는 것은 1부터 N까지 각각의 카드 수 구매 시 금액의 최댓값을 얻는 것이다.

이것도 점화식만 잘 구하면 되는 것이었다.

dp[1] = price[1]  # 3
dp[2] = dp[1] + price[1] or dp[0] + price[2] # 8
dp[3] = dp[1] + p[2] or dp[2] + price[1] or dp[3] + price[0] # 15

즉, 위 점화식은 다음과 같이 일반화할 수 있다.

$ dp[i] = dp[i - j] + p[j] $

 

식 중에서 가장 큰 값을 저장해주면 되는 일이었다.

 

---

🤔 후기

아직 동적 프로그래밍 문제를 많이 풀어본 것은 아니지만, 점화식이 핵심이라는 것은 슬슬 보인다.

점화식만 잘 세우면 코드는 어렵지 않게 짤 수 있을 듯 한데...모르겠다. 더 연습이 필요할듯