[이취코테] 효율적인 화폐 구성

https://youtu.be/5Lu34WIx2Us

이 문제의 해설 영상이다.

문제

N가지 종류의 화폐 중에서 화폐의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 한다. (화폐 개수는 무제한이며 순서가 달라도 같은 걸로 친다)

 

입력 조건

• 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

 

출력 조건: 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다 (불가능할 때는 -1을 출력한다).

 

정답 코드

import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
cost = [int(sys.stdin.readline().rstrip()) for i in range(n)]

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

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

DP 문제이다 보니까 핵심은 점화식을 세우는 것이다. 

예를 들어 현재 화폐 단위가 2와 3이 있다고 가정하면 m을 만드는 최소 개수는 m - 2를 만드는 최소 개수와 m - 3을 만드는 최소 개수 중 더 작은 값에 1을 더한 값이 된다. 이를 점화식으로 나타내면 d[j] = min(d[j], d[j - cost[i]] + 1)으로 나타낼 수 있다.

 

m의 최대 크기가 10,000이므로 만들 수 없는 경우를 나타내는 수로 10,001을 사용하여 초기 dp 리스트를 초기화해준다.

그다음 첫 번째 화폐부터 차례대로 확인하면서 dp 리스트를 갱신해나가면 된다.

 

배울 점

처음 이 문제를 봤을 때 그리디의 대표 문제인 거스름돈 문제가 생각이 났다. 하지만 화폐 단위에서 큰 단위가 작은 단위의 배수일 때만 그리디로 풀 수 있다는 조건을 확인하고 dp로 접근하기 위해 노력했다.

 

dp 문제를 계속 풀고 있지만 항상 풀이를 참고해야 할 정도로 점화식을 생각해내고 구현하는 것이 너무 어렵게 느껴진다.

다양한 문제를 접해보면서 더 노력해야겠다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)