효율적인 화폐 구성

N가지 종류의 화폐가 있다

이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다

이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다

 

입력조건

→ 첫째 줄에 N,M이 주어진다 (1<=N<=100, 1<=M<=10,000)

→ 이후 N개의 줄에는 각 화퍠의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다

 

출력조건

→ 첫째 줄에 M원을 만들기 위한 최소한의 화퍠 개수를 출력한다.

→ 불가능할 때는 -1을 출력한다.

n, m = map(int, input().split())
unitMoney = []
for i in range(n):
    unitMoney.append(int(input()))
array = [10001] * (m + 1)
array[0] = 0
for i in range(n):
    for j in range(unitMoney[i], m + 1):
        if array[j - unitMoney[i]] != 10001:
            array[j] = min(array[j], array[j - unitMoney[i]] + 1)
if array[m] == 10001:
    print(-1)
else:
    print(array[m])