효율적인 화폐 구성 (파이썬) / DP(다이나믹 프로그래밍)

문제

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

"INPUT"
2 15
2
3

"OUTPUT"
5

"INPUT"
3 4
3
5
7

"OUTPUT"
-1

입력

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

 

출력

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

---

풀이

풀이의 핵심은 DP 점화식을 세우는 것이다.

d[i] = min(d[i], d[i-화폐단위] +1) 의 점화식을 유의하고 처리하면 된다.

import sys

sys.stdin = open("input_7-5.txt","r")
sys.stdout = open("output_7-5.txt","w")

# input
n, m = map(int, input().split())
maximum = 10001
money_list= []
for _ in range(n):
    money_list.append(int(input()))

# DP용 리스트
d = [maximum] * (m + 1)

# 값 처리
d[0]= 0
d[min(money_list)] = 1
for i in range(min(money_list), m+1):
    for money in money_list:
        # 음수가 되면 중단
        if i-money < 0:
            break
        else:
            d[i] = min(d[i], d[i-money]+1) # 최소값 갱신

# 출력불가시
if d[m] == maximum:
    print(-1)
# 그외
else:
    print(d)