문제 설명

N가지 종류의 화폐가 있을때, 화폐 개수를 최소한으로 해서 M원을 만드는 방법의 개수?

IN
N M N가지 종류의 화폐 총 M원 만들기
n1
n2
... N가지 화폐의 단위

OUT
경우의 수 없으면 -1

문제 풀이

M원을 만들기 위해서
적은 금액 ~ 큰 금액까지 차례대로 확인한다.
$a_i$ : i를 만들 수 있는 최소 화폐 개수
$k$ : 화폐의 단위 라고 했을때
점화식은
$a_{i-k}$ = $a_i = min(a_k, a_{i-k}+1)$ $a_{i-k}$ 만들 수 있음 or 10001

코드

n, m = map(int, input().split())
money = []
for _ in range(n):
    x = int(input())
    money.append(x)

dp = [10001] * (m+1)
dp[0] = 0

for i in range(n):
    for j in range(money[i], m+1):
        if dp[j-money[i]] != 10001:
            dp[j] = min(dp[j], dp[j-money[i]]+1)
if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])