[python] 효율적인 화폐 구성

- N가지 종류의 화폐

- 개수 최소한으로 이용해서 합이 M원

- 최소 화폐 개수 출력

 

n, m = map(int, input().split())  # 화폐 개수, 가치의 합
# N개의 화폐 단위 정보
array = []
for i in range(n):
    array.append(int(input()))

# DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍 (보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# =결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])