C++で金額Nを支払うために必要なコインの最小枚数を求める方法

問題の概要

数値 N が与えられ、額面が 1、10、25 のコインがそれぞれ無限にあるものとします。このとき、ちょうど N を支払うために必要なコインの最小枚数を求めます。

例えば、N が 14 の場合、答えは 5 枚になります。10 の硬貨 1 枚と 1 の硬貨 4 枚を組み合わせれば、合計 14 をちょうど支払えるためです。

アルゴリズムの考え方（貪欲法）

この問題は、価値の大きいコインから優先的に使う「貪欲法（Greedy法）」で効率的に解くことができます。手順は以下のとおりです。

• N < 10 の場合： 1 の硬貨を N 枚使えばよいので、答えは N 枚となります。
• 9 < N < 25 の場合： まず 10 の硬貨をできるだけ多く（N ÷ 10 の商の枚数）使い、残額（N % 10）は 1 の硬貨で支払います。両者を合計したものが答えです。
• N ≥ 25 の場合： まず 25 の硬貨をできるだけ多く（N ÷ 25 の商の枚数）使い、残額（N % 25）に対して再び同じ処理を再帰的に繰り返します。

この貪欲法は、1・10・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 の場合、まず 25 の硬貨を 3 枚（計 75）使い、残額は 13 になります。この 13 に対しては 10 の硬貨 1 枚と 1 の硬貨 3 枚で支払えるため、合計枚数は 3 + 1 + 3 = 7 枚となります。

このように、大きい額面から順に割り当てていくシンプルな再帰処理だけで、最小枚数を求めることができます。金種が限られている両替問題やお釣り計算など、実務でも応用範囲の広いアルゴリズムです。