[백준] [Python] 2294번 동전2 - DP

https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

 

Python

#import math
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
coins = list(set([ int(input()) for _ in range(n)]))
coins.sort()

nums = [float("inf")]*(m+1)
nums[0] = 0

for x in range(1, m+1):
    for c in coins:
        if x-c >= 0:
            nums[x] = min(nums[x], nums[x-c]+1)

    
if nums[m] == float("inf"):
    print(-1)
else:
    print(nums[m])