Chapter 08 DP - 효율적인 화폐 구성

https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

[226p 효율적인 화폐 구성]

 

import sys

INF = 10001

n, m = map(int, sys.stdin.readline().rstrip().split())
coins = []

for _ in range(n):
    coins.append(int(sys.stdin.readline().rstrip()))

d = [INF] * (m + 1)
# 각 코인으로 만들 수 있는 경우를 1로 만들기 위해 d[0] = 0으로 설정
d[0] = 0

for i in range(1, m + 1):
    for k in coins:
        # 현재 만들 수 있는 금액이 코인보다 커야한다.
        if i >= k:
            # 각 코인으로 만들 수 있는 경우 중 최솟값
            d[i] = min(d[i], d[i - k] + 1)

# INF가 아니면 만들 수 있다는 의미미으로 해당 값 출력
# INF이면 만들 수 없다는 의미이므로 -1을 출력
print(d[m] if d[m] != INF else -1)