コイン両替最小枚数

額面の決まったコインを組み合わせて、指定された金額ちょうどを作ります。使う枚数を最も少なくするのが目標で、どう組み合わせても作れない金額なら -1 を返します。

大きい額から使うと、2 枚で済むところが 3 枚になる

コインが 1、3、4 円の 3 種類、作りたい金額が 6 円だとします。大きいほうから使うと、まず 4 を取り、残り 2 円を 1 円 2 枚で埋めて合計 3 枚です。ところが 3 円を 2 枚使えば 2 枚で済みます。

大きいほうから取る手は、日本の硬貨のように額面が都合よく並んでいるときだけ当たります。額面が自由に決まる以上、最初の 1 枚を決め打ちで選ぶことはできません。

最後の 1 枚を決め打ちして、残りは任せる

選べないなら、全部試します。6 円を作る最後の 1 枚が何だったかで場合分けします。

5 円、3 円、2 円それぞれの最小枚数さえ分かっていれば、そこへ最後の 1 枚を足した 3 つの値のうち、一番小さいものが 6 円の答えです。5 円の答えも同じやり方で 4、2、1 円から決まります。金額を 1 円から順に決めていけば、見に行く先は必ず先に決まっています。

出発点は 0 円で、使う枚数は 0 枚です。

作れないことを 0 で表すと、それが選ばれてしまう

2 円玉しかないのに 3 円を作れ、という金額が途中に現れます。ここを 0 にしておくと、最小値を選ぶ場面で 0 が一番小さい値として選ばれ、作れないはずの金額から答えが組み立てられてしまいます。

作れないことは、絶対に選ばれない大きな値で表します。

print(min(float('inf'), 3))   # 3 が選ばれる
print(float('inf') + 1)       # inf のまま

console.log(Math.min(Infinity, 3));   // 3
console.log(Infinity + 1);            // Infinity

無限大は何を足しても無限大なので、+ 1 を通しても「作れない」の印が消えません。最後まで無限大のままだったら、その金額は本当に作れなかった、と判定できます。

やってみよう

ひな形の TODO を完成させてください。使える額面の判定と最小枚数の遷移を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

例として額面 [2, 5] で 7 を作るなら、最後が 2 の場合は 5 の答えに一枚、最後が 5 の場合は 2 の答えに一枚を足します。どちらも二枚です。正の額面では amount + 1 を未到達の印にできます。表の確保と結果の整形は用意し、使える額面の判定・候補の計算・比較と更新を書きます。

1. 使える額面の判定と最小枚数の遷移を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える