[이코테] 효율적인 화폐 구성

문제

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

M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하라.

입력 조건

첫째 줄에 N,M이 주어진다. ($1 \leq N \leq 100$, 1 $1 \leq M \leq 10,000 $)

이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

첫째 줄에 최소 화폐 개수를 출력한다.

불가능할 때는 -1을 출력한다.

입출력 예

Example 1:

Input: 
2 15
2
3
Output: 
5

Example 2:

Input:
3 4
3
5
7
Output:
-1

풀이과정

내 풀이

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

li = []
for _ in range(n):
	li.append(int(input()))

d = [1e9]*(m+1)

for i in range(1,m+1):
    for j in li:
        # 나누어 떨이진다면?
        if i % j == 0:
            d[i] = min(d[i], i // j)
            
        # 더했을 때가 더 낫다면?
        if i-j >= 1:
            d[i] = min(d[i], d[i-j]+1)

if d[m] == 1e9:
    print(-1)
else:
    print(d[m])

책 풀이를 보고나니 나누어 떨어진 경우를 따로 하지 않아도 되겠다고 판단이 되었다.

책 풀이

$a_i$ = 금액 $i$를 만들 수 있는 최소한의 화폐 개수

$k$ = 각 화폐의 단위

점화식: 각 화폐 단위인 $k$를 하나씩 확인하며

• $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_{i} = min(a_i,a_{i-k}+1)$
• $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_i = INF$

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
    array.append(int(input()))
    
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m+1):
        if d[j - array[i]] != 10001:	# (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)
            
# 계산된 결과 출력
if d[m] == 10001	# 최종적으로 M원을 만드는 방법이 없는 경우
	print(-1)
else:
    print(d[m])