문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

# 2294
import sys
input = lambda: sys.stdin.readline().strip()

n, k = map(int, input().split())
coin = sorted([int(input()) for _ in range(n)])
knapsack = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    wi = coin[i-1]
    if wi <= k:
        knapsack[i][wi] = 1
        
    for j in range(k+1):
        if j-wi >= 0:
            value1 = knapsack[i][j-wi]
            if value1 > 0 or wi == j:
                value1 += 1
            value2 = knapsack[i-1][j]
            
            if value2 == 0:
                knapsack[i][j] = value1
            elif value1 == 0:
                knapsack[i][j] = value2
            else:
                knapsack[i][j] = min(value1, value2)
        else:
            knapsack[i][j] = knapsack[i-1][j]
            
if knapsack[n][k]:
    print(knapsack[n][k])
else:
    print("-1")

백준 2294 동전 2