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

문제

www.acmicpc.net/problem/2294

2294번: 동전 2

 

 

풀이 및 소스코드

k의 최댓값이 10000이기 때문에 dp 리스트를 10001으로, 0원을 택하는 방법은 없으므로 dp[0] = 0으로 초기화시킨다.

동전의 최소 갯수를 구해야하기때문에 dp[j] 와 dp[j-coin[i]]+1 을 비교해서 최솟값을 넣도록한다.

import sys
input = sys.stdin.readline

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

coin = [int(input()) for _ in range(n)]

dp = [10001]*(k+1)
dp[0] = 0
for i in range(n):
    for j in range(coin[i], k+1):
        dp[j] = min(dp[j], dp[j-coin[i]]+1)

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