BOJ - 2294 - 동전 2

import sys

INF = 1e9

def solution():
    N, K = map(int, sys.stdin.readline().split())
    coin = []
    for _ in range(N):
        coin.append(int(sys.stdin.readline()))
    coin = sorted(list(set(coin)))
    dp = [INF] * (10001)
    dp[0] = 0
    for i in range(1, K+1):
        for c in coin:
            if i - c < 0:
                break
            dp[i] = min(dp[i], dp[i - c] + 1)

    print(dp[K] if dp[K] != INF else -1)
solution()

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