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

bled 2021. 5. 8. 10:19

www.acmicpc.net/problem/2294

2294번: 동전 2

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주

www.acmicpc.net

[코드]

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])