[동적계획법] 난이도2, 이취코 226p '효율적인 화폐 구성' (Python)

<문제>

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

<입력 조건>

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

<출력 조건>

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

---

<문제 풀이>

1. 보텀업 방식으로 문제 풀기

 

<코드>

#이취코 답
n,m = 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])

 

<고쳐야 할 점>

• 테스트케이스 이외에 케이스도 고려하기
• 동적계획법 보텀업 방식 기억하기
• 복습 알고리즘