동전 2 (백준 2294, 파이썬)

 

 

다이나믹 프로그래밍 문제다.

d[n] = n원을 만들기 위해 사용하는 동전의 최소 개수로 두고 짰다.

k원을 만들기 위해 필요한 동전 수는 d[k]가 된다.

import sys
 
n, k = map(int, sys.stdin.readline().split())
coin = []
 
for i in range(n):
    coin.append(int(sys.stdin.readline()))
 
coin.sort()
d = [0]*(k+1)
 
for i in range(coin[0], k+1):
    temp = []
    if i in coin:
        d[i] = 1
    else:
        for j in coin:
            if i-j >= coin[0]:
                if d[i-j] != -1:
                    temp.append(d[i-j]+1)
        if len(temp) >0:
            d[i] = min(temp)
        else:
            d[i] = -1
 
print(d[k])