효율적인 화폐 구성

출처:: 

분류:: 다이나믹 프로그래밍 

 

1. 문제 이해 및 해결과정

- 그리디의 거스름돈 문제와거의 동일하나 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점이 다르다 - 그리디처럼, 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 , 다이나믹 프로그래밍을 이용해야한다. -  구현  1) a(i-k) 를 만드는 방법이 존재하는 경우, a(i) = min(a(i),a(i-k)+1)  2) a(i-k) 를 만드는 방법이 존재하지 않는 경우, a(i) = 21470000000(큰 수)

 

2. 풀이방법

  1.bottom-up

 

#효율적인 화폐 구성
#
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
coin=[]
INF=2147000000
#dp테이블 
dp=[INF]*(m+1)
for i in range(n):
    coin.append(int(input()))
#for x in coin:
#    dp[x]=1
dp[0]=0
for i in range(coin[0],m+1):
    for j in range(len(coin)):
        if i%coin[j]==0:
            dp[i] = min(dp[i - coin[j]] + 1, dp[i])

if dp[m]!=INF:
    print(dp[m])
else:
    print(-1)

3. 오답원인

 

4. 알게된 점