-
N가지 종류의 화폐가 있다. -
화폐들의 개수를 최소한으로 이용해서 그 가치의 합이
M원이 되도록 하려고 한다.- 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
예를 들어,
2원,3원 단위의 화폐가 있을 때는15원을 만들기 위해
3원을5개 사용하는 것이 가장 최소한의 화폐 개수이다.
-
입력조건
-
첫째 줄에
N, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000 ) -
이후
N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가피는 10,000보다 작거나 같은 자연수이다.
-
-
출력조건
-
첫째 줄에
M원을 만들기 위한 최소한의 화폐 개수를 출력한다. -
불가능할 때는
-1을 출력한다.
-
1. 타뷸레이션을 이용한 풀이
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input()))
d = [10001] * (m + 1) #dp테이블 초기화
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
-
이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다.
- 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.
-
이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다.
-
금액
i를 만들 수 있는 최소한의 화폐 개수를aᵢ, 화폐의 단위를k라고 했을때 다음과 같이 점화식을 작성할 수 있다.-
aᵢ₋ₖ(금액(i - k)를 만들 수 있는 최소한의 화폐 개수)를 만드는 방법이 존재하는 경우,aᵢ = min(aᵢ, aᵢ₋ₖ + 1 ) -
aᵢ₋ₖ를 만드는 방법이 존재하지 않는 경우,aᵢ = 10,001
-
-
-
이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다.
-
실제로 문제를 풀기 위해서는 가장 먼저
K의 크기만큼 리스트를 할당한다. -
이후에 각 인덱스를 '금액'으로 고려하여 메모이제이션을 진행한다.
-
-
예를들어
N = 3,K = 7이고, 각 화폐의 단위가2, 3, 5인 경우를 생각해보자.0) 초기화
-
각 인덱스에 해당하는 값으로
10,001을 설정한다.-
10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다.- 이보다 더 큰 수여도 상관 x
-
0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로0을 설정한다.
-
-
초기 리스트 값은 다음과 같다.
1) 화폐단위: 2, 3, 5
-
먼저 2부터 확인한다.
-
점화식에 따라 다음과 같이 리스트가 갱신된다.
-
예를 들어 인덱스
2의 경우1이라는 값을 가지는데, 이는2원짜리 화폐 하나를 이용하여2원을 만들 수 있다는 의미이다. 즉a₂= a₀ + 1이다. -
인덱스
4의 경우2라는 값을 가지는데, 이는2원짜리 화폐 2개를 이용하여(2 + 2) = 4원을 만들 수 있다는 의미이다. 즉a₄= a₂+ 1이다.
-
-
10,001의 값을 그대로 가지는 경우는2원짜리 화폐를 가지고 구성할 수 없는 금액이기 때문이다.
**2) 화폐단위: 2, 3, 5** -
이어서 3을 확인한다.
-
다음과 같이 리스트가 갱신된다.
- 예를 들어 `a₅ = a₂+ 1`로 `2`라는 값을 가진다. 이것은 `2`원짜리 화폐 1개, `3`원짜리 화폐 1개로 `(2 + 3) = 5`원을 만들 수 있다는 의미가 된다.
<br/>3) 화폐단위: 2, 3, 5
-
이어서 5를 확인한다.
-
다음과 같이 리스트가 갱신된다.
-
예를 들어
a₇ = a₂+ 1로2라는 값을 가진다. 이는2원짜리 화폐 1개,5원짜리 화폐 1개로(2 + 5) = 7원을 만들 수 있다는 의미가 된다.-
이전 단계에서
a₇의 값은3이었는데, 이는(2 + 2 + 3) = 7원으로 3개의 화폐를 사용했을 때를 나타낸 것이다. -
다만, 현재 단계에서
(2 + 5) = 7원을 만들면 화폐 2개만 사용해도 되므로, 더 작은 값으로 갱신된다.
-
-
-
-
2. C++ 코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> arr;
int main(void) {
// 정수 N, M을 입력받기
cin >> n >> m;
// N개의 화폐 단위 정보를 입력 받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
vector<int> d(m + 1, 10001);
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i]; j <= m; j++) {
// (i - k)원을 만드는 방법이 존재하는 경우
if (d[j - arr[i]] != 10001) {
d[j] = min(d[j], d[j - arr[i]] + 1);
}
}
}
// 계산된 결과 출력
if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
cout << -1 << '\n';
}
else {
cout << d[m] << '\n';
}
