문제 정의
금액 N이 주어지고, 가치가 각각 1, 10, 25인 세 종류의 동전을 무제한으로 보유하고 있다고 가정해 봅시다. 이때 정확히 N의 금액을 지불하기 위해 필요한 최소 동전 개수를 구하는 것이 목표입니다.
예를 들어 N이 14라면, 10짜리 동전 한 개와 1짜리 동전 네 개, 즉 총 5개의 동전으로 지불할 수 있습니다.
해결 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가능한 한 큰 단위의 동전을 먼저 최대한 많이 사용하고, 남은 금액은 더 작은 단위의 동전으로 처리하는 것입니다. 구체적인 단계는 다음과 같습니다.
- N이 10 미만인 경우: 모든 금액을 1짜리 동전으로만 지불합니다. 따라서 필요한 동전 개수는 곧 N개입니다.
- N이 10 이상 25 미만인 경우: 금액을 10으로 나눕니다. 몫은 10짜리 동전의 개수가 되며, 나머지 금액은 1짜리 동전으로 커버합니다. 두 값을 더하면 답이 됩니다.
- N이 25 이상인 경우: 금액을 25로 나누어 몫만큼 25짜리 동전을 사용하고, 나머지 금액에 대해 위 과정을 재귀적으로 반복합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int countMinCoins(int n) {
if(n < 10)
return n;
else if(n > 9 && n < 25){
int count = n / 10;
count += n % 10;
return count;
} else {
int count = n / 25;
return count + countMinCoins(n % 25);
}
}
int main() {
int n = 88;
cout << "Minimum number of coins required: " << countMinCoins(n);
}
실행 결과
Minimum number of coins required: 7
동작 원리 상세 분석
N = 88일 때 알고리즘이 어떻게 작동하는지 단계별로 살펴보겠습니다.
- 88 ÷ 25 = 3 (나머지 13) → 25짜리 동전 3개 사용
- 13은 10 이상 25 미만이므로, 13 ÷ 10 = 1 (나머지 3) → 10짜리 동전 1개 사용
- 남은 3은 10 미만이므로 → 1짜리 동전 3개 사용
따라서 전체 동전 개수는 3 + 1 + 3 = 7개가 되어 실행 결과와 일치합니다.
참고 사항
이 그리디 방식은 1, 10, 25처럼 단위 간 배수 관계가 잘 맞는(canonical) 동전 체계에서 항상 최적해를 보장합니다. 하지만 일반적인 임의의 동전 체계에서는 그리디 접근이 최적해를 보장하지 못할 수 있으므로, 그런 경우에는 동적 계획법(Dynamic Programming)을 활용하는 것이 더 안전합니다.