[인프런] 동전교환

---

문제설명

다음과 같이 여러 단위의 동전들이 주어질 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 단, 각 단위의 동전은 무한정 사용할 수 있다. 만약 3개의 동전인 1원, 2원, 5원이 주어졌다고할 때, 15원을 만들 수 있는 가장 적은 수의 동전 개수는 3개이다.(5원 5원 5원)

입력조건

• 첫 줄에는 동전의 종류개수 N(1<= N <= 12)이 주어진다.
• 둘째 줄에는 N개의 동전의 종류가 주어지고, 그 다음주에 거슬러 줄 금액 M(1 <= M <= 500)이 주어진다.
• 각 동전의 종류는 100원을 넘지 않는다.

출력조건

• 첫 줄에 거슬러 줄 동전의 최소개수를 출력한다.

사고과정

• 냅색 알고리즘을 배운 뒤에는 구현이 쉬웠다. 이 문제에서도 중복을 허용하기 때문에 DP 테이블을 Bottom-up 방식으로 앞에서부터 구현해나가면 된다.
• 단, 내 풀이에서는 정확히 M원을 만들 수 없는 경우도 따로 처리해보았다.

풀이

coins = list(map(int, input().split()))
m = int(input())
INF = int(1e8)
dp = [INF] * (m+1)
dp[0] = 0

for coin in coins:
    for j in range(coin, m+1):
        dp[j] = min(dp[j], dp[j - coin] + 1)
# 만약 정확히 m원을 만들 수 없는 경우를 따로 처리해야 하는 경우
if dp[m] == INF:
    print(f'정확히 {m}원을 만들 수 없음')
else:
    print(dp[m])