서로 다른 동전의 목록 C(c₁, c₂, …, cₙ)와 목표 금액 V가 주어졌을 때, 이 문제는 가장 적은 수의 동전을 사용하여 금액 V를 만드는 방법을 찾는 것입니다.
참고: 각 종류의 동전은 무한개 있다고 가정합니다.
이 문제에서는 동전의 종류가 C{1, 2, 5, 10}으로 주어지며, 각 동전은 무한개 사용할 수 있습니다. 요청된 금액을 만들기 위해 어떤 종류의 동전이든 가장 적은 개수를 사용하려고 합니다. 예를 들어 금액이 22라면 {10, 10, 2}, 즉 3개의 동전이 최소 개수가 됩니다.
입력과 출력
입력: 목표 금액. 예: 48 출력: 필요한 최소 동전 개수. 여기서는 7. 48 = 10 + 10 + 10 + 10 + 5 + 2 + 1
알고리즘
이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 0부터 목표 금액까지 각 금액 i를 만드는 데 필요한 최소 동전 개수를 배열에 저장합니다.
- 금액 i를 만들 때, 사용 가능한 각 동전 c에 대해 '금액 (i − c)를 만드는 최소 동전 수 + 1'을 계산합니다.
- 모든 동전 후보 중 가장 작은 값을 선택하여 coins[i]에 저장합니다.
minCoins(coinList, n, value)
입력: 서로 다른 동전 목록, 동전의 개수 n, 목표 금액 value
출력: 목표 금액을 만들기 위한 최소 동전 개수
Begin
if value = 0, then
return 0
define coins array of size value + 1, fill with ∞
coins[0] := 0
for i := 1 to value, do
for j := 0 to n, do
if coinList[j] <= i, then
tempCoins := coins[i-coinList[j]]
if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then
coins[i] := tempCoins + 1
done
done
return coins[value]
End알고리즘 설명
- 초기화: 금액이 0일 때 필요한 동전은 0개이므로 coins[0] = 0으로 설정하고, 나머지 값은 모두 무한대(∞)로 초기화합니다.
- 점화식 적용: 금액 1부터 목표 금액까지 순회하면서, 각 동전 coinList[j]가 현재 금액 i보다 작거나 같은 경우 coins[i − coinList[j]] + 1을 계산합니다.
- 최솟값 갱신: 계산된 값이 기존 coins[i]보다 작으면 갱신합니다.
- 결과 반환: 최종적으로 coins[value]에 저장된 값이 답입니다. 만약 무한대 그대로라면 해당 금액은 주어진 동전으로 만들 수 없음을 의미합니다.
C++ 예제 코드
#include<iostream>
using namespace std;
int minCoins(int coinList[], int n, int value) {
int coins[value+1]; // 금액 i를 만드는 최소 동전 개수 저장
if(value == 0)
return 0; // 금액이 0이면 필요한 동전은 0개
coins[0] = 0;
for (int i=1; i<=value; i++)
coins[i] = INT_MAX; // 초기에는 0을 제외한 모든 값을 무한대로 설정
for (int i=1; i<=value; i++) { // 1부터 목표 금액까지 최솟값 탐색
for (int j=0; j<n; j++)
if (coinList[j] <= i) {
int tempCoins = coins[i-coinList[j]];
if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
coins[i] = tempCoins + 1;
}
}
return coins[value]; // 목표 금액에 필요한 동전 개수 반환
}
int main() {
int coins[] = {1, 2, 5, 10};
int n = 4, value;
cout << "Enter Value: "; cin >> value;
cout << "Minimum "<<minCoins(coins, n, value)<<" coins required.";
return 0;
}실행 결과
Enter Value: 48 Minimum 7 coins required.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(value × n)입니다. 여기서 value는 목표 금액, n은 동전의 종류 수입니다. 금액 1부터 목표 금액까지 각 단계에서 모든 동전 종류를 확인하기 때문입니다. 공간 복잡도는 금액별 최소 동전 수를 저장하는 배열 때문에 O(value)입니다.
단순히 큰 동전부터 우선적으로 사용하는 그리디(Greedy) 방식도 있지만, 동전 체계에 따라 항상 최적해를 보장하지 못합니다. 예를 들어 동전이 {1, 3, 4}이고 금액이 6인 경우, 그리디 방식은 {4, 1, 1}로 3개를 선택하지만 실제 최적해는 {3, 3}으로 2개입니다. 따라서 항상 최적해를 보장하려면 위와 같은 동적 계획법 접근이 필요합니다.