난이도

Gold 4

문제

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

입력

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

출력

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

예제 입력

3 15
1
5
12

예제 출력

3

해설

배낭 문제와 비슷한 형식의 문제이다. 일반적으로 거스름돈 문제는 Greedy하게 O(K)정도 수준으로(거스름돈의 종류에만 의존하므로) 어주 빠르게 해결할 수 있었는데, 이 문제는 동전간의 관계가 배수가 아니므로 DP로 해결해야 한다. 그렇기 때문에 동전의 조합으로 만들어낼 수 없는 값도 존재하는데, 그럴 때에 -1을 출력해야 한다. 나는 바텀 업 방식으로 풀이하면서 해당 d리스트 인덱스에 해당하는 가치를 만들 수 없을 경우 매우 큰 수를 대입하도록 하여 해결했다. 동전의 가치의 한계가 정해져 있으므로 정당한 풀이 방식이라고 생각한다.

제출 코드

import sys

n,m = map(int, sys.stdin.readline().rstrip().split())
coins = [] #화폐 단위
for i in range(n):
    coins.append(int(sys.stdin.readline().strip()))


d = [0 for i in range(m+1)]
for i in range(min(coins)):
    d[i] = 9999999 #방법이 없으므로

for i in range(min(coins),m+1):
    #print(d)
    if(i in coins):
        d[i] = 1
        continue
    minVal = 9999999
    for j in coins:
        if(i-j>=0):
            if(minVal > d[i-j]):
                minVal = d[i-j] + 1
    d[i] = minVal

#print(d)
if(d[m] >= 9999999):
    print('-1')
else:
    print(d[m])