백준 2294 파이썬 python : 동전 2 @@황소처럼 우직하게@@ 바이브타면서~

생각해보자

동전의 종류는 1원, 5원, 12원

자,

15원을 만들고 싶어

그러면

14원에서 1원을 더하거나, 10원에서 5원을 더하거나, 3원에서 12원을 더하거나

음 구현해보자

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
lst = []
dp = [999999999] * (k + 1)
dp[0] = 0
for _ in range(n):
   lst.append(int(input()))

lst.sort()
for price in lst:
    for i in range(price, k + 1):
        dp[i] = min(dp[i - price] + 1, dp[i])
print(dp[-1] if dp[-1] != 999999999 else -1)