백준 2294 동전 2 / python

문제 : 2294

풀이 point

예제로 예를 들자면
1 2 5 동전 3개가 있을 때
k원을 만들기 위해 x원 동전이 몇개 필요한지를 세어준다.

k : 1 -> 1원 1개
k : 2 -> min(1원 2개, 2원 1개)
k : 3 -> min(1원 3개, 1원1개 + 2원 1개)

즉 15원을 만들기 위해서
1원 : dp = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

2원은 만들기 위한 k-2를 빼준 값에 +1을 해주면 된다.
-> 3원까지 만든 동전 개수 + 1을 한 값이 5원을 만든 동전 개수가 됨을 이해하자.
1원의 동전 개수도 그 전에 포함되어 있으니 min을 통해 동전 개수가 가장 적게 드는 경우를 채택한다.
2원 : dp = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8]

5원도 마찬가지로 진행한다.
5원 dp: [1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3]

풀이 코드

N, K = map(int, input().split())

dp = [999999]*(K+1)

coin = []

dp[0] = 0

for _ in range(N):
  coin.append(int(input()))

for c in coin:
  for i in range(c, K+1):
    dp[i] = min(dp[i], dp[i-c]+1)

print(dp[K] if dp[K] != 999999 else -1)

사족

K원을 만들기 위해 [K-1]까지 구하면 +x를 해서 구할 수 있나? 까지는 생각했지만 $2\times2$ 같은 곱하기에 사로잡혀서 어떻게 점화식을 구해야할지 헤맸던 것이 아쉽다.