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

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

2294번: 동전 2

 

<풀이>

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coin = [int(input()) for _ in range(n)]
INF = int(1e9)
dp = [INF for _ in range(k+1)]
dp[0] = 0

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

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

 

dp문제

해당 금액에 도달할 수 있는 최소값을 저장해두고 더 적은 개수로 도달할 수 있으면 패치해준다.

coin을 리스트에 저장해두고 min( dp[i], dp[i-c]+1) 로 비교해서 dp[i]를 패치해준다.