C++ 그리디 알고리즘으로 주어진 금액의 최소 지폐 개수 구하기

금액이 하나 주어졌을 때, 서로 다른 액면가의 지폐를 조합하여 정확히 그 금액을 만들 수 있는 최소 개수의 지폐를 구하는 문제를 생각해 봅시다. 핵심 아이디어는 가장 큰 액면가의 지폐부터 시작해, 주어진 금액 범위 안에서 가능한 한 많은 장수를 사용하는 것입니다.

이때 {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} 각 액면가의 지폐는 무한히 보유하고 있다고 가정합니다. 예를 들어 금액이 800이라면 필요한 지폐는 500 1장, 200 1장, 100 1장, 총 3장이 됩니다.

그리디(Greedy) 접근법

이 문제는 그리디 알고리즘으로 해결할 수 있습니다. 그리디 기법은 매 단계에서 당장 가장 유리한 선택(여기서는 가장 큰 액면가 사용)을 반복하는 전략입니다. 동작 과정은 다음과 같습니다.

1. 지폐 배열을 큰 액면가 → 작은 액면가 순으로 순회합니다.
2. 남은 금액이 현재 지폐의 액면가보다 크거나 같으면, 그 액면가로 낼 수 있는 최대 장수를 구합니다(amount / notes[i]).
3. 사용한 금액만큼 남은 금액에서 차감한 뒤, 다음 액면가로 넘어갑니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void countNotes(int amount) {
    // 액면가를 내림차순으로 나열한 지폐 배열
    int notes[10] = { 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
    int noteFreq[10] = { 0 }; // 지폐별 사용 장수

    for (int i = 0; i < 10; i++) {
        if (amount >= notes[i]) {
            noteFreq[i] = amount / notes[i];   // 해당 액면가의 최대 장수
            amount -= noteFreq[i] * notes[i];  // 남은 금액 갱신
        }
    }

    cout << "Note count:" << endl;
    for (int i = 0; i < 10; i++) {
        if (noteFreq[i] != 0) {
            cout << notes[i] << " : " << noteFreq[i] << endl;
        }
    }
}

int main() {
    int amount = 1072;
    cout << "Total amount is: " << amount << endl;
    countNotes(amount);
}

실행 결과

Total amount is: 1072
Note count:
500 : 2
50 : 1
20 : 1
2 : 1

결과 분석

금액 1072는 다음과 같이 구성됩니다.

• 500 × 2 = 1000
• 50 × 1 = 50
• 20 × 1 = 20
• 2 × 1 = 2

합계 1000 + 50 + 20 + 2 = 1072이며, 총 5장의 지폐로 목표 금액을 만들 수 있습니다.

시간 복잡도

지폐 종류가 n개일 때 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 지폐별 장수를 저장하는 배열 때문에 공간 복잡도 역시 O(n)입니다.

참고: 그리디 알고리즘이 항상 최적이 아닌 경우

표준 화폐 체계처럼 액면가가 잘 설계된(canonical) 경우에는 그리디 방식이 항상 최소 장수를 보장하지만, 임의의 액면가 집합에서는 그렇지 않을 수 있습니다. 예를 들어 액면가가 {1, 3, 4}이고 금액이 6이라면, 그리디는 4 + 1 + 1(총 3장)을 선택하지만 실제 최적해는 3 + 3(총 2장)입니다. 이런 경우에는 동적 계획법(DP)을 사용하는 것이 안전합니다.