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

1000単位、500単位、100単位、50単位、20単位、10単位、5単位、2単位、1単位という9種類の額面を持つ通貨システムがあると仮定します。

特定の金額が与えられたとき、その金額をちょうど合計できる紙幣の最小枚数を計算する関数を作成する必要があります。

例

たとえば、金額が 512 の場合を考えてみましょう。

512 を構成する最小の紙幣の組み合わせは以下のとおりです。
・500 単位 × 1 枚
・10 単位 × 1 枚
・2 単位 × 1 枚

この場合、関数は合計枚数である 3 を返す必要があります。

解決のアプローチ：貪欲法（グリーディアルゴリズム）

この種の問題は「貪欲法」と呼ばれる手法で効率的に解けます。考え方はシンプルで、可能な限り大きな額面から順番に優先して使うというものです。

具体的には、各額面について「その額面で何枚支払えるか」を計算し、残りの金額を次に小さい額面へ引き継いでいきます。1・2・5系で構成される一般的な通貨体系では、この方法で常に最小枚数が得られることが保証されています。

なお、額面ごとに if 文を大量に連ねて1枚ずつ減算していく書き方も可能ですが、額面の配列を用意してループで一括処理するほうが、コードが格段に簡潔になり、新しい額面への対応や保守も容易になります。

コード例

const countNotes = sum => {
  // 大きい額面から順に並べた配列
  const denominations = [1000, 500, 100, 50, 20, 10, 5, 2, 1];
  let count = 0;

  for (const note of denominations) {
    // 現在の額面で支払える最大枚数をまとめて加算
    count += Math.floor(sum / note);
    // 支払った分だけ残額を更新
    sum %= note;
  }
  return count;
};

console.log(countNotes(512));   // 3
console.log(countNotes(7845));  // 14

出力結果

コンソールには以下のように出力されます。

3

コードのポイント

• Math.floor(sum / note) により、その額面を最大何枚使えるかを一度に求められます。
• sum %= note で支払い後の残額を計算し、次の小さい額面へ引き渡します。
• 各額面を1回ずつ処理するだけでよいため、1枚ずつ減算していく方式に比べてループ回数が大幅に減り、可読性とパフォーマンスの両方が向上します。

このように貪欲法を活用すれば、紙幣の最小枚数を求める問題を短く明快なコードで解決できます。