출처: 백준 온라인 저지
https://www.acmicpc.net/problem/2293
점화식 자체를 구성하지 못해서 못 풀었다. DP의 핵심은 점화식 구성인데, 그게 안 되는 문제는 계속 붙잡고 있어도 안 되는 것 같다. DP 문제를 생각보다 더 많이 풀어봐야겠다.
문제 풀이
위 영상을 보고나서야 원리를 제대로 이해할 수 있었다.
k원짜리 동전을 만드는 경우의 수를 f(k)라고 하자.
1, 2, 5원 동전으로 10원을 만드는 경우를 생각해보자.
우선 1원짜리 동전만 포함시키는 경우를 생각해야 한다. 이 경우는 1원부터 10원까지 모두 한 가지 방법만 존재한다. (1원짜리 동전 k개) 따라서 f(1) = f(2) = ... f(10) = 1이다.
다음으로 2원을 추가하여, (1원, 2원)으로 k원을 만드는 경우를 생각해보자. 2원짜리 동전을 하나 이상 포함해서 k원을 만들기 위해서는 (1원, 2원)으로 k-2원을 만든 다음 2원을 추가해야 한다. 그래서 이 경우의 수는 f(k-2)와 같다.
(1원, 2원)으로 k원을 만드는 방법은 2가지다. 하나는 2원을 포함시키지 않는 방법이고, 다른 하나는 2원을 포함시키는 방법이다. 그런데 이전에 1원짜리만으로 k원을 만드는 경우의 수를 미리 계산했고, 그 값이 f(k)다. 따라서 여기에 2원을 포함하여 (1원, 2원)으로 k원을 만드는 경우의 수, 즉 f(k-2)를 더하기만 하면 된다.
이런 식으로 하나씩 동전을 추가시키고, t원짜리 동전을 추가할 때 f(k) += f(k-t)의 점화식을 적용하면, 결국 f(k)의 값은 주어진 동전으로 k원을 만들 수 있는 경우의 수가 된다.
정답 코드
from sys import stdin
n, k = map(int, stdin.readline().split())
coins = []
for _ in range(n):
coins.append(int(stdin.readline()))
count_list = [0] * (k + 1)
# x원짜리 동전 하나로 x원을 만드는 경우의 수 = 1
count_list[0] = 1
for i in coins:
for j in range(i, k + 1):
count_list[j] += count_list[j - i]
print(count_list[k])