お釣り

説明

コインの合計金額が正しいお釣りの金額と等しくなるように、お客さんに渡すコインの枚数が最も少なくなる組み合わせを求めましょう。

例

• 入力が15で、硬貨が[1, 5, 10, 25, 100]のときは、5セント硬貨（5）1枚と10セント硬貨（10）1枚、つまり[5, 10]を返します。
• 入力が40で、硬貨が[1, 5, 10, 25, 100]のときは、5セント硬貨（5）1枚と10セント硬貨（10）1枚と25セント硬貨（25）1枚、つまり[5, 10, 25]を返します。

エッジケース

• 与えられたどんな硬貨の組み合わせでも、アルゴリズムは正しく動くでしょうか？
• マイナスのお釣りを求められることはあるでしょうか？
• 最も小さい硬貨の金額より小さいお釣りを求められることはあるでしょうか？

---

出典

Software Craftsmanship - Coin Change Kata