문제
N가지 종류의 화폐 중에서 화폐의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 한다. 화폐 갯수는 무제한이며 순서가 달라도 같은 걸로 친다.
불가능시 -1을 출력한다.
✍️ 풀이
기본적인 그리디 문제처럼 거스름돈 문제와 동일하지만 화폐단위의 큰 단위가 작은 단위의 배수가 아니라는 점이 다르다.
따라서, 그리디로 해결할 수 없으며 다이나믹 프로그래밍을 이용해야만 한다.
문제에서 최소한의 화폐 갯수로 원하는 금액을 만들라고 했으므로
i. 현재 화폐단위로 구성 가능한 경우 (a(i-k) 존재시 a(i) = min(a(i), a(i-k) + 1)
ii. 현재 화폐단위로 구성 불가능한 경우 a(i) = 10001 (구성할 수 있는 것보다 더 큰 수)작은 화폐 단위부터 구성할 수 있는 화폐의 갯수를 센다.
화폐 단위가 점점 커지면서 더 적은 수로 값을 구성할 수 있을 때만 갱신하도록 한다.
🛠 코드
n, m = map(int, input().split())
val = [int(input()) for _ in range(n)]
print(val)
d = [10001]*10001
d[0] = 0
for v in val:
for j in range(v, m+1):
d[j] = min(d[j], d[j-v]+1)
print(d[m])📝 정리
- DP...
🎈 참고
Go Go