[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

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))