任意の金額をちょうど支払うための最小硬貨枚数を計算するワンライナー

0〜999円の買い物に対して、釣り銭の無いよう支払うためには硬貨が最低で何枚必要か、という問題を考える。


最初に考えたものは、

perl -le'$a=pop;$a-=$_*($:=int($a/$_)),$b+=$:for(500,100,50,10,5,1);print$b'

というもの。

$ perl -le'$a=pop;$a-=$_*($:=int($a/$_)),$b+=$:for(500,100,50,10,5,1);print$b' 999
15

普通に割り算を使って、元の金額から引いていって、…と繰り返す。


でもまぁ使うのが日本の貨幣で、枚数が最小になるという前提なら100,10,1円玉は4枚以下、500,50,5円玉は1枚以下になるはずだし、ということで

perl -le'$a=pop;$c+=$a/$_%($b++%2?5:2)for(500,100,50,10,5,1);print$c'

というのも考えてみた。これならいちいち引き算する必要がなくなる。

$ perl -le'$a=pop;$c+=$a/$_%($b++%2?5:2)for(500,100,50,10,5,1);print$c' 999
15


それぞれの枚数を出力する場合は

perl -le'$a=pop;$c->{$_}=$a/$_%($b++%2?2:5)for(1,5,10,50,100,500);print"$_:$c->{$_}"for sort{$b<=>$a}keys%$c'

で。

$ perl -le'$a=pop;$c->{$_}=$a/$_%($b++%2?2:5)for(1,5,10,50,100,500);print"$_:$c->{$_}"for sort{$b<=>$a}keys%$c' 999
500:1
100:4
50:1
10:4
5:1
1:4


しかしこの方法では、20円玉とか30円玉とかが登場してしまうと破綻する。
どんな硬貨が新規に登場しても大丈夫なようにするなら一番最初のが良いのかもしれない。


ていうかもっと他に良い方法はないだろうか。

追記

Wassrでアイデアをいただいた。
http://wassr.jp/user/graywolf8192/statuses/c3ywDafXBD

perl -le'$a+=$_%5+$_/5%5for pop=~/./g;print$a'

これは短い!なるほどー、日本円の単位だと桁ごとに区切って考えてしまうことができるんですね。

$ perl -le'$a+=$_%5+$_/5%5for pop=~/./g;print$a' 999
15