[Dynamic Programming] 동전 2

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

Description

n가지 가치가 다른 종류의 동전이 있다. 가치의 합이 k원이 되면서 동전의 개수가 최소가 되는 경우를 찾는 문제이다. 동전의 개수의 최솟값을 출력하고 불가능하면 -1을 출력한다.

Idea

dp[k] : k원을 만드는데 필요한 최소 동전 수 dp[k]는 k보다 작은 dp값들로부터 구해질 수 있어서, k 값이 1일때부터 k일때까지 차례로 올라가면 된다.

Pseudocode

for i : 1 ~ k dp[i] = 1 + min(

1. dp[i - value] ( i > value )
2. 0 ( i = value )
3. inf ( i < value )

for value in values) i = value 일때 0값을 갖는 이유는 결국 1을 더해주어 dp[i] 값이 1이 되게 하기 위함이다.

Code

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

def solve(k, dp, values):     for i in range(1, k+1):         dp[i] = min([case(i, dp, value) for value in values]) + 1       return [dp[k], -1][dp[k] == 10000]   def case(i, dp, value):     if i > value:         return dp[i - value]     elif i == value:         return 0     else:         return 10000   if __name__ == '__main__':     #parse input     n, k = [int(i) for i in input().split()]     values = [int(input()) for _ in range(n)]       #make dp list     dp = [10000] * (k+1)       #answer     print(solve(k, dp, values))