C++で指定した金額を作るのに必要な紙幣の最小枚数を求める方法

問題概要

ある金額が与えられたとき、その金額ちょうどになるように、異なる額面の紙幣の最小枚数を求めます。基本的な考え方は、最も高額な紙幣から順に、残りの金額に対してできる限り多くの枚数を充てていくというものです。

ここでは、{2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} の各額面が無限に用意されているものとします。例えば、金額が 800 の場合は「500 × 1枚、200 × 1枚、100 × 1枚」の計 3 枚が答えになります。

解き方：貪欲法（Greedy）

この問題は貪欲法を使うことで効率的に解くことができます。手順は以下の通りです。

1. 額面を大きい順に並べた配列を用意します。
2. 各額面について、現在の残額をその額面で割った商を、使用枚数として採用します。
3. 残額から使用済みの金額を差し引き、より小さい額面へ進みます。
4. これをすべての額面に対して繰り返します。

{2000, 500, 200, …} のような標準的な通貨体系では、この貪欲法が常に最小枚数の解を導くことが知られています。

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 = amount - noteFreq[i] * notes[i];
        }
    }
    cout << "Note count:" << endl;
    for (int i = 0; i < 9; 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

処理の流れ（amount = 1072 の場合）

• 1072 ÷ 500 = 2 枚使用 → 残額 72
• 72 ÷ 50 = 1 枚使用 → 残額 22
• 22 ÷ 20 = 1 枚使用 → 残額 2
• 2 ÷ 2 = 1 枚使用 → 残額 0

この結果、合計 5 枚の紙幣で 1072 を表すことができます。

計算量

額面の種類数を N とすると、時間計算量は O(N) です。今回のように額面が固定されている（10 種類）ため、実質的には定数時間 O(1) で動作します。