「今週のお題：現地で使いやすい両替」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力される整数 m ( m≦50000 ) に対して、m 円をできるだけ多くの種類の貨幣 ( 硬貨・紙幣 ) で構成した上で、それぞれの枚数の合計をできるだけ少なくするとき、合計の最小値を計算し出力する。なお、貨幣は、1円、5円、10円、50円、100円、500円、1000円、2000円、5000円、10000円の10種とする。
ちなみに、合計を少なくするのと、種類を多くするのとでは、後者の方が優先になります。
そのため、例えば m=11254 であれば、単純に最も枚数の少ない9枚 ( 10000×1+1000×1+100×2+50×1+1×4 の5種 ) ではなく、19枚 ( 5000×1+2000×2+1000×1+500×2+100×1+50×2+10×4+5×2+1×4 の9種 ) が正しい答えとなります。
解説
以下のRubyのコードを提出しました。
p ->m{
cur=[1,5,10,50,100,500,1000,2000,5000,10000]
acc=cur.each_with_object([0]){|e,r|r.push(r[-1]+e)}
cur.size.downto(2).reduce(0){|s,i|s+((m>=acc[i]?m-acc[i-1]:[m-acc[i-2],0].max)/cur[i-1]).tap{|x|m-=x*cur[i-1]}}+m
}[gets.to_i]
基本的な考え方として、金額の大きい貨幣から数を決めていきます。
ここで先に、ちゃんと種類を最大にするにはどうすれば良いか、が問題になるのですが、実は何種類になるかはすぐにわかります。なぜなら、小額の貨幣から 1 枚ずつ選んでいって、どこで入力の金額より溢れるか、を見れば良いからです。
例えば、全貨幣の合計 18666円以上あれば全部がカバーできて10種類ですし、1～2000円の合計8666円以上で、そこから5000円足した13666円に満たないのであれば8種類といった具合にです。
そこで、もし18666円以上の金額であれば、10000円より小額の貨幣を1枚ずつ確保した8666円を除いた中から、10000円札を単純にできるだけ多く抜いていけば済むことになります。10000円札を抜いたら、今度は3666円を除いた中から5000円札を抜いていく、そういった感じです。
問題は、13666円のように、5000円以下はカバーできるが10000円まではカバーできず、さりとて10000円に手が届かないわけではない、というケースです。すなわち、5000×2+2000×1+1000×1+500×1+100×1+50×1+10×1+5×1+1×1 の9種10枚と、10000×1+2000×1+1000×1+… の9種9枚の比較になる訳です。
しかし、よくよく考えてみると、種類が同じであれば、より高額の貨幣を選んだ方が合計を減らすことができると分かります。なので、8666円ではなく3666円を確保した上で10000円を抜く ( 5000円は諦める ) という選択になります。
この理屈は、より小額の貨幣の枚数を決める時でも同じです。なので、この方法で金額の大きい貨幣から決めて抜いていき、最後に残った金額を1円にあてることで、最終的な合計枚数を求めることができます。
終わりに
紙幣だと2000円の存在がイレギュラーだったりして、どう場合分けしたものか色々悩んだのですが、気付いてみれば貨幣に依存した場合分けもなく、非常にすっきり書けて満足しました。
