[Python] 백준 #2294- 동전 2 [try_again]

문제

---

2294번: 동전 2

코드

---

Another answer

import sys
r = sys.stdin.readline

N, K = map(int, r().split())
coins = sorted([int(r()) for _ in range(N)])

dp = [10001] * (K+1)
dp[0] = 0

for i in range(N):
    for j in range(coins[i], K+1):
        dp[j] = min(dp[j], dp[j-coins[i]] + 1)

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

 

풀이

---

동전1문제랑 비슷할 줄 알았는데 못풀었다.. 우선 기본적인 방법은 비슷하다. 현재 값에서 가진 동전의 값을 빼주었을 때의 동전 사용 개수에 지금 동전 개수 하나를 더한 값과 이전 동전들로만 조합했을 때 사용된 동전 개수를 비교하여 더 작은 값을 dp배열에 담는다. 마지막 조건문은 해당금액을 만들 수 없을 때 -1을 출력하는 것이다.