2294 - 동전 2 [DP]

출처 : 백준 2294 동전 2

문제

동전 2는 Greedy 알고리즘으로 푼 (백준-11047-동전) 문제와 조건이 유사하다. 다만, 주어지는 동전들의 값 때문에 Greedy로 풀면 정확한 답을 얻을 수 없고 DP로만 풀 수 있다. 동전들과 동전으로 만들어야하는 값이 있을 때 최소의 동전들을 사용해서 그 값을 맞춰야하는 것이 문제이다. 예를 들어서, 맞춰야 하는 값이 8이고 주어진 동전들이 [1, 4, 6]일 때, Greedy로 풀면 큰 값으 먼저 채우기 때문에 6, 1, 1이 될 것이고, DP로 풀면 4,4 이기 때문에 DP로만 최소 동전의 수를 구할 수 있게 된다.

맞춰야하는 값이 10000은 넘지 않는다고 했기 때문에 처음에 DP를 사용할 배열을 10001로 초기화 해야 한다. DP를 사용할 배열의 길이는 맞춰야하는 값 + 1, 즉, K+1만큼이어야 한다. 0은 어떤 동전으로도 맞출 수 없기 때문에 배열의 0번째 index에 0을 저장한다.

for loop안에 있는 연산이 하는 것은 현재 자신의 값 & coin의 값만큼 뺀 index의 값에다 1을 더한 값을 비교해서 더 작은 값을 자신의 값으로 저장한다. 이 loop가 모든 동전들의 종류와 맞춰야 하는 값까지 진행이 되면 배열의 맨 마지막 값은 맞춰야하는 값을 주어진 동전을 최소로 활용해서 만들 수 있는 수를 의미하게 된다.

풀이

import sys
r = sys.stdin.readline

N, K = map(int, r().split())
coins = sorted([int(r()) for _ in range(N)])

arr = [10001] * (K+1)
arr[0] = 0

for i in range(N):
    for j in range(coins[i], K+1):
        arr[j] = min(arr[j], arr[j-coins[i]] + 1)

arr[-1] = arr[-1] if arr[-1] != 10001 else -1
print(arr[-1])