[이코테] 다이나믹프로그래밍 - 효율적인 화폐 구성

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

N가지 종류의 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록하려고 한다. 이 때 각 화폐는 몇 개라도 사용가능하며 사용한 화폐의 구성은 같지만 순서가 다른 것은 같은 경우로 구분한다.

입력조건

• 첫째 줄에 N, M이 주어진다.(1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

출력조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

사고과정

• 몹시 어려웠다. DP 테이블을 어떻게 활용할지 감도 안왔다. 해설을 보니 최소 화폐 개수를 DP 테이블로 생성하되 화폐 단위별로 loop를 돌면서 DP 테이블을 업데이트 시켜주는 방식으로 구현됨.
• 인상적인 부분은 만약 6원을 만들기 위해 2원 화폐를 사용하는 최소 화폐 개수 $a_6$을 구하는 방식을 $a_6 = a_{6-2} + 1$ 즉, $a_6 = a_4 + 1$로 나타내며, 여기서 +1이 2원 화폐를 '한 번' 사용한 것을 의미. 즉 해당 원소를 관련있는 직전의 원소와 관련된 점화식으로 나타낸 것임..
• 화폐 단위 마다 비교하면서 최소 화폐 개수를 DP 테이블에 유지 또는 갱신시키면서 DP 테이블의 인덱스 M번의 요소값(M원에 해당하는 값)을 출력하도록 한다.

풀이

import sys

N, M = map(int, input().split())
currency = [int(input()) for _ in range(N)]
# DP 테이블
d = [10001] * (M+1)
d[0] = 0  # 0원일 경우

for c in range(len(currency)):
	for j in range(currency[c], M+1):
    	if d[j - currency[c]] != 10001:
        	# 화폐 단위마다 갱신
        	d[j] = min(d[j], d[j - currency[c]] + 1)
 
if d[M] == 10001:
 	print(-1)
else:
	print(d[M])