[Python] BOJ / 2294번 / 동전 2

2294번: 동전 2

---

📝 풀이

• 입력이 다음과 같이 주어졌을 때

3 15
1
5
12

• 각각의 가치를 만드는데 필요한 동전의 최소 개수는 아래와 같다.
  • 0: 0 (0)
  • 1: 1 (1)
  • 2: 1, 1 (2)
  • 3: 1, 1, 1 (3)
  • 4: 1, 1, 1, 1 (4)
  • 5: 5 (1)
  • 6: 1, 5 (2)
  • 7: 1, 1, 5 (3)
  • 8: 1, 1, 1, 5 (4)
  • 9: 1, 1, 1, 1, 5 (5)
  • 10: 5, 5 (2)
  • 11: 1, 5, 5 (3)
  • 12: 12 (1)
  • 13: 1, 12 (2)
  • 14: 1, 1, 12 (3)
  • 15: 5, 5, 5 (3)
• 따라서 다음과 같은 점화식이 성립한다.
  • dp[i] = min(dp[i], dp[i - coin[i]] + 1)
  • 여기서 dp[i]는 i원을 만드는데 필요한 동전의 최소 개수를 의미한다.

---

💻 소스 코드

import sys

input = sys.stdin.readline
INF = sys.maxsize

n, k = map(int, input().split())
coin = []
for _ in range(n):
    coin.append(int(input()))

# dp[i] : i원을 만드는데 필요한 동전의 최소 개수
dp = [0] + [INF] * 10000

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] != INF else -1)