효율적인 화폐구성

문제

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

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

출력
첫째 줄에 경우의 수 X를 출력한다.(불가능할 때는 -1을 출력한다)
입력 예시

2 15
2
3

출력 예시

5

나의 풀이

이 문제와 비슷한 문제로 화폐의 종류가 서로 배수 관계인 경우 탐욕법을 사용해 해결할 수 있는 문제가 있으나 이 문제는 화폐 종류가 정해지지 않아 동적계획법을 사용해 최소한의 개수를 구하도록 생각했다.

점화식을 찾기 위해 입력 예시를 사용해 직접 확인해 보았다.
0 1 2 3 4 5 6 7 8
0 -1 1 1 2 2 2 3 3
0~8까지 최소 개수를 세어본 결과 위의 결과가 나오게 되었는데 이 표를 분석한 결과
6의 경우 6-2 => 4의 최소개수 + 1 = 3, 6-3 => 3의 최소개수 + 1 = 2 중 작은 값인 2가 6이 될수 있는 최소한의 동전을 사용한 상태란 것을 알 수 있었다.

따라서 점화식은 $a_{i} = min(a_{i-k}, a_{i})$ 이고 불가능한 경우를 -1이라고 하게 되면 min값이 -1이 되는 문제가 생기므로 주어진 최대값에 1을 더한 10001을 사용하여 이를 해결했다.

위의 내용을 바탕으로 bottom up 방식을 사용해 코드를 구현했다.

코드

n, m = map(int, input().split(' '))

money = []
MAX_INT = 10001

for i in range(n):
    money.append(int(input()))

dp = [MAX_INT] * (m + 1)

dp[0] = 0

for i in range(1, n):
    for j in range(money[i], m + 1):
        if dp[j - money[i]] != MAX_INT:
            dp[j] = min(dp[j], dp[j - money[i]] + 1)

if dp[m] == MAX_INT:
    print(-1)
else:
    print(dp[m])