[다이나믹 프로그래밍] 효율적인 화폐 구성

본 글은 아래 나봉빈 43:22 효율적인 화폐 구성 문제 풀이입니다!

https://youtu.be/5Lu34WIx2Us?feature=shared

---

import sys
input=sys.stdin.readline

n,m=map(int, input().split())
array=[]
for i in range(n):
  array.append(int(input()))

#다이나믹을 사용해야하는 이유:
#1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있다
#    -> 동전의 개수를 점차 늘려나가며 그 개수를 최소화하는 개수를 구할 수 있다.
#2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.
#    -> 동전의 부분합을 여러번 써서 최소 화폐 개수를 계산해야 함.

d=[10001]*(m+1) #0원부터 m원까지의 금액에 대한 최소한의 화폐 개수를 구하기 위해 

d[0]=0 #아무것도 사용안해도 만들 수 있는 금액 = 0

for k in array: #k는 각각의 화폐 단위
  #n의 최솟값이 1이기 때문에 m이 1인 경우의 최소 화폐 개수는 무조건 1임  
  for i in range(k, m+1):  #i는 각각의 금액
    #a_i = 금액 i(최종적으론 m)를 만들 수 있는 최소한의 화폐 개수 (m을 만들기 위해 작은 문제 i부터 해결)
    #k = 각 화폐
    
    #점화식 : 
    #  a_(i-k)를 만드는 방법이 존재하는 경우(i에서 k를 뺀 금액을 만들 수 있다면) : a_i=min(a_i, a_(i-k) + 1) <-현재 i의 화페개수와 i에서 k를 뺀 금액의 화폐개수에 1을 더한 값 중 더 작은 것
    #      1을 더하는 이유 : i에서 k를 뺀 금액의 화폐개수가 현재 i의 화폐개수보다 적다면 k라는 화폐를 하나 더 추가하는 것이기 때문
    if d[i-k] != 10001: #i-k원을 만드는 방법이 존재하는 경우
      d[i]=min(d[i], d[i-k]+1)    
    #  a_(i-k)를 만드는 방법이 존재하지 않는 경우 : a_i=INF 
    #      여기서 INF는 10001로 이미 초기화 되어 있음

#계산된 결과 출력
if d[m]==10001:
  print(-1)
else:
  print(d[m])