[백준 2294] 동전 2 with Python

문제 링크

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

2294번: 동전 2

풀이

import sys

n, k = map(int, sys.stdin.readline().split())
coin = [int(sys.stdin.readline()) for _ in range(n)]
dp = [10001 for _ in range(k+1)]
dp[0] = 0
for i in range(1, k+1):
    for j in coin:
        if i < j: continue
        dp[i] = min(dp[i], dp[i-j] + 1)

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

dp[n]은 n원을 만들기 위해 필요한 동전의 최소 개수를 나타낸다.

 

a원짜리 동전을 포함해서 n원을 만든다고 했을 때,

dp[n] = dp[n-a] + 1이라고 할 수 있다.

 

예를 들어, 3원짜리 동전을 하나 선택해서 10원을 만드는 동전의 최소 개수는

dp[7](7원을 만드는 동전의 최소 개수) + 1(3원짜리 동전 1개)이다.

 

그런데 어떤 동전을 포함할 때가 가장 적은 수의 동전이 필요한 지 알려면 모든 동전에 대해 위의 과정을 거쳐야 한다.

예를 들어 동전 종류가 총 3개로 1원, 5원, 8원이라면

dp[n] = min(dp[n-1], dp[n-5], dp[n-8]) + 1이 성립한다.

단, 이 때 동전의 가치는 n보다 작거나 같아야 한다.

예를 들어 dp[6]을 구할 때 8원은 포함할 수 없기 때문이다.

 

dp를 앞에서부터 순회하면서 채워나가면 최종적으로 dp[n]을 구할 수 있다.

이 때, dp[0] = 0으로 초기화하여 가장 작은 가치의 동전을 선택했을 경우에도 정상적으로 dp를 구할 수 있도록 한다.

그리고 dp[i] = min(dp[i], dp[i-j] + 1)을 가장 첫 번째 동전을 선택했을 때는 dp[i]의 초기값과 dp[i-j]+1을 비교하게 되는데, 이 때 dp[i]의 초기값이 dp를 구하는데 영향을 끼치지 않기 위해 k 입력값의 최댓값인 10000보다 큰 값으로 초기화하였다.