[python] 효율적인 화폐 구성

- N가지 종류의 화폐

- 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 함

 

=> 경우의 수 출력

 

n, m = map(int, input().split())

data = []
for i in range(n):
    data.append(int(input()))

d = [10001] * (m+1)

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