[다이나믹 프로그래밍] 이코테 (파이썬) 효율적인 화폐 구성 풀이

[문제]

N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다.

 

이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.

 

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

 

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

 

[입력 조건]

1. 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)

 

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

 

[출력 조건]

첫째 줄에 최소 화폐 개수를 출력한다. 불가능할 때는 -1을 출력한다.

<입력 예시 1>
2 15
2
3
<출력 예시 1>
5

<입력 예시 2>
3 4
3
5
7
<출력 예시 2>
-1

 

[풀이]

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

arr = []
for i in range(n) :
  arr.append(int(input()))

d = [10001] * (m + 1)

d[0] = 0
for i in range(n) :
  for j in range(arr[i], m + 1) :
    if d[j - arr[i]] != 10001 :
      d[j] = min(d[j], d[j - arr[i]] + 1)
  
if d[m] == 10001 :
  print(-1)
else :
  print(d[m])

 

우선 정수 n과 m을 공백으로 구분하여 입력받고 n개의 화폐 단위 정보 또한 입력받는다.

 

그 후 한 번 계산된 결과를 저장하기 위한 다이나믹 프로그래밍 테이블(d)을 초기화해준 뒤 금액이 0원이라면 0개의 

 

화폐가 사용되기 때문에 테이블의 0번쨰 원소에 값을 0으로 할당해준다.

 

그리고 다이나믹 프로그래밍을 수행하는데 반복문을 활용하여 현재 금액에서 현재 확인하고 있는 화폐 단위의 금액을 뺀

 

그 금액을 만들 수 있다면 그 금액을 만든 optimal solution에서 1을 더한 값과 현재의 값과 비교하여 더 작은 값으로

 

갱신할 수 있도록 한다. 이러한 과정을 반복하고 최종적으로 계산된 결과를 출력하는데,

 

만약 M원을 만드는 방법이 없는 경우 즉, 값이 10001이라면 -1을 출력하고 그렇지 않다면 그대로 그 값을 출력한다.

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저