2294 동전2 파이썬

문제

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

2294번: 동전 2

 

소스코드

import sys
n, k = map(int, sys.stdin.readline().split())
dp = [10001] * (k+1)
dp[0] = 0
coin = []
for _ in range(n):
    coin.append(int(input()))

for c in coin:
    for p in range(c, k+1):
        if p-c >= 0:
            dp[p] = min(dp[p], dp[p-c]+1)

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

2293번 동전1문제와 유사하다

dp는 합이 p일때, 최소 동전의 개수이다.

최소값을 구하라 했으니 dp 배열의 초기값을 크게 잡고 합이 0일때는 0이다.

dp[p] = min(dp[p], dp[p-c]+1)

p일때 최소 값을 넣어주기 위해 이전 동전에서 구했던 dp[p]와 dp[p-c]+1의 최솟값을 dp[p]에 넣어준다

dp[p-c]+1은 현재 동전 상태에서의 p일때 동전개수와 같다