알고리즘/DP

[Python] 백준 2294 - 동전 2

o_onn5 2023. 1. 19. 07:46
728x90

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

 

2294번: 동전 2

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

www.acmicpc.net

동전1 문제 풀면 동전2는 금방 풀 수 있다. 

역시

재밌다.

 

INF = 987654321

n,k = map(int,input().split())

coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [INF]* (k+1)

dp[0] = 0

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

if dp[k] == INF:
    print(-1)
else:
    print(dp[k])
728x90