효율적인 화폐 구성

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

---

문제 내용

• N가지 종류의 화폐가 있음
• 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 함
• 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분

입력 조건

• 첫째 줄에 N, M이 주어짐 $(1 \le N \le 10,000)$
• 이후 N개의 줄에는 각 화폐의 가치가 주어짐
• 화폐의 가치는 10,000보다 작거나 같은 자연수

출력 조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력
• 불가능할 때는 -1을 출력

입력 예시 1

2 15
2
3

출력 예시 1

5

입력 예시 2

3 4
3
5
7

출력 예시 2

-1

---

문제 해설

• 화폐 단위에서 큰 단위가 작은 단위의 배수가 아님
• 그렇기 때문에 그리디 알고리즘처럼 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용하면 됨
• 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 됨
• 금액 $i$를 만들 수 있는 최소한의 화폐 개수를 $a_i$, 화폐의 단위를 $k$라고 했을 때 다음과 같은 점화식을 작성할 수 있음
• $a_{i-k}$는 금액 $(i-k)$로 만들 수 있는 최소한의 화폐 개수를 의미
  • $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_i = min(a_i, a_{i-k} - 1)$
  • $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_i = 10,001$
• 이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 됨
• 실제로 문제를 풀기 위해서는 가장 먼저 M의 크기만큼 리스트를 할당
• 이후에 각 인덱스를 금액으로 고려하여 메모이제이션을 진행

예시

• N = 3, M = 7, 화폐의 단위 = 2, 3, 5

Step 0 - 초기화

• 각 인덱스에 해당하는 값으로 10,001을 설정, 10,001은 특정 금액을 만들 수 있는 화폐 구성이 없다는 것을 의미
• 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값을 0으로 설정

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	10,001	10,001	10,001	10,001	10,001	10,001

Step 1 - 화폐 단위: 2

• 첫 번째 화폐 단위인 2부터 확인
• 점화식에 따라 다음과 같이 리스트 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	10,001	2	10,001	3	10,001

• $a_2 = a_0 + 1$
• $a_4 = a_2 + 1$
• $a_6 = a_4 + 1$

Step 2 - 화폐 단위: 3

• 이어서 화폐 단위 3을 확인
• 점화식에 따라 다음과 같이 리스트 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	1	2	2	2	3

• $a_3 = a_0 + 1$
• $a_5 = a_2 + 1$
• $a_6 = a_3 + 1$
• $a_7 = a_4 + 1$

Step 3 - 화폐 단위: 5

• 이어서 화폐 단위 5를 확인
• 점화식에 따라 다음과 같이 리스트 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	10,001	1	1	2	1	2	2

• $a_5 = a_0 + 1$
• $a_7 = a_2 + 1$

소스 코드

# 정수 N, M을 입력받기
n, m = map(int, input())
# 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])