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

• 문제 : https://www.acmicpc.net/problem/2294
• Dynamic Programming (DP)

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

dp = [10001] * (m + 1)
dp[0] = 0

for c in coins:
    for i in range(c, m+1):
        dp[i] = min(dp[i], dp[i - c] + 1)

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