[백준] 2294번 - 동전2 (파이썬)

www.acmicpc.net/problem/2294

2294번: 동전 2

[코드]

N, K = map(int, input().split())

coin_type = []
for i in range(N):
    coin_type.append(int(input()))
coin_type = set(coin_type)

dp = [10001] * 10001
dp[0] = 0

for coin in coin_type:
    if 0 <= coin <= 10001:
        dp[coin] = 1

for i in range(1, K + 1):
    for coin in coin_type:
        if i - coin >= 0:
            dp[i] = min(dp[i], dp[i - coin] + 1)

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