高速おつり計算

　おや、こういうお金の出し方(財布内枚数最小化法?)って普通かと思ってた。もっとも、俺の場合はもうちょっと違うなぁ(数式化すると本質は同じだと思うけど)。927円の買い物に1032円出す例だと……

  1. 1000円出すとお釣りが73円になる。
  2. 手元に10円硬貨が3枚(以上)あるので、このままではバラ銭が50円分出来てしまう。
  3. ではもう30円出そう。
  4. するとお釣りが103円になるが、1円硬貨も2枚あるので、バラ銭で5円が出来る。
  5. ということでもう2円出そう。

　俺の場合を分析するとこんな感じかな? つまり、いま出してる金額に対するお釣りで、以下のどれかのパターンが出来てしまうなら、その分を上乗せして払う、というアルゴリズムか。

  • 1円硬貨・10円硬貨・100円硬貨・1000円札が5枚
  • 5円硬貨・50円硬貨・500円硬貨・5000円札が2枚