[백준/Python] 2294 동전 2

문제 링크

2294번: 동전 2

 

문제 풀이

• 동전이 1만 있다면 다음과 같이 작성할 수 있다.

n	0	1	2	3	4	5	...	14	15
dp[n]	0	1	2	3	4	5	...	14	15

• 동전이 1, 5가 있다면 5이상부터는 값이 달라진다.

n	0	1	...	5	6	7	...	14	15
dp[n]	0	1	...	1	2	3	...	6	3

• n이 5일 때, 1을 5번 사용하는 것보다 5를 1번 사용하는 것이 최소로 사용하기 때문이다.
• 각 동전의 값부터 시작하여 계산한다. 현재 위치(i)에서 동전 값(coin)만큼 뺀 위치(i-coin)의 값(dp[i-coin])에서 1을 더한 값과 현재 위치의 값(dp[i])를 비교하여 더 작은 값을 저장하도록 한다.

 

전체 코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = [int(sys.stdin.readline().strip()) for _ in range(n)]

dp = [100001] * (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[-1] == 100001:
    print(-1)
else:
    print(dp[-1])