문제
N가지 종류의 화폐가 있다. 이 화폐들을 최소한으로 사용해 합이 M원이 되도록 하고자 한다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오.
조건
입력조건
1. 첫째 줄에 N,M이 주어진다.
2. 이후의 N개 줄에는 각 화폐의 가치가 주어진다.
출력조건
1. 첫째 줄에 최소 화폐 개수를 출력한다.
2. 불가능할 때는 -1을 출력한다.
코드
n,m = list(map(int,input().split()))
array=[]
for i in range(n):
array.append(int(input()))
d=[10001]*(m+1)
d[0]=0
for i in range(n):
for j in range(array[i],m+1):
if d[j-array[i]]!=10001:
d[j] = min(d[j],d[j-array[i]]+1)
if d[m]==10001:
print(-1)
else:
print(d[m])
풀이
각 화폐 종류마다 0원 부터 원하는 금액 M원까지 만들 수 있는 화폐 갯수를 다이나믹 리스트에 저장한다.
화폐 종류 갯수만큼 반복하여 화폐를 적게 사용해 해당 금액을 만족시킬 수 있을 경우 작은 값으로 치환한다.
예를 들어 본 문제를 쉽게 풀자면
화폐 단위가 2, 3, 5로 구성되어 있을 때 2원짜리부터 만들 수 있는 경우의 수를 쫙 깐다. 그 후 3원 짜리로 만들 수 있는 경우의 수를 동일한 다이나믹 리스트에 매핑한다. 이 때 6원 같이 2원과 3원 둘 다 조합하여 만들 수 있는 경우에는 기존의 것이나 앞에서 만든 3원의 값에서 +1 해준 값을 비교해 더 적은 값을 최종적으로 매핑한다. 이 과정을 2,3,5원 모두 반복하면 최종적으로 M원 이내의 모든 금액이 구현할 수 있는 최소의 지폐 개수로 매핑된다. 여기서 d[m]만 뽑아 쓰는 것이다.
진짜 다이나믹 프로그래밍이 코테 준비할 때 1차적으로 닥치는 난관같다. 디버깅을 해보면서 흐름을 이해해도, 백지에 다시 구현코자 하면 아직 쉽지 않다 .. 갈 길이 멀다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
