[이코테] 다이나믹 프로그래밍_효율적인 화폐 구성 (python) (푸는 중)

문제

: n가지 종류의 화폐 존재. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 m원이 되도록 하려고 함.
-> 그리디 문제처럼 보이지만, 그리디에서는 큰 단위가 작은 단위의 배수였음. 여기서는 아니기 때문에 다이나믹 프로그래밍으로 풀어야함!

나의 풀이

1. 작성중 but 아이디어부터 틀려먹음~!

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
num = list(int(input()) for _ in range(n))
d = [m + 1] * (m + 1)
def money(n, m, x, arr):
    if d[x] != m + 1:
        return d[x]
    d[0] = 0
    for k in arr:
		before = [0]
        if x >= k and money(n, m, x - k, arr) != m + 1:
            before.append(money(n, m, x - k, arr) + 1)
		else:
			 before.append(m + 1)
        d[x] = min(d[x], *before)
    
    if d[x] == m + 1:
        return -1
    else:
        return d[x]
print(money(n, m, m, num))