[코테] 백준 다이나믹 프로그래밍 2294번 문제

2294번 : 동전 2

문제 링크

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

문제 설명

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

문제풀이

사용하는 동전을 하나씩 늘리면서 합이 k원인 이전 최소 횟수보다 해당 동전을 사용했을 때의 횟수가 더 작다면 갱신한다.

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
memos = [0] + [1000001] * k

for coin in coins :
    for i in range(1, k+1) : 
        if i - coin >= 0 :
            memos[i] = min(memos[i], memos[i-coin] + 1)

if memos[-1] == 1000001 : 
    print(-1)
else : 
    print(memos[k])