[파이썬] [DP] 효율적인 화폐 구성

N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 만들어라. 각 화폐는 몇 개라도 사용할 수 있다.

 

a. 예를 들면

2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해서는 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수다.

 

b. 입력 조건

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

c. 출력 조건

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

코드

# 정수 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])