読者です 読者をやめる 読者になる 読者になる

「今週のお題:枚数で考えるパスカルの三角形」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

入力 n に対し、パスカルの三角形の n 段目の各数値を日本円とみなし、それぞれを硬貨 ( 1円、5円、10円、50円、100円、500円 )・紙幣 ( 1000円、2000円、5000円、10000円 ) 最小枚数で用意した場合、その枚数の合計を出力するものです。

解説

実装

提出版のRuby(104)です。

(s=q=1).upto(m=n=gets.to_i){t=m;3.times{s+=t/5%2+t%5;t/=10};s+=t/10+t/5%2+(t%5+1)/2;m*=n-=1;m/=q+=1}
p s

コードのコメントをそのまま流用して説明します。

パスカルの三角形ということは、combination演算の結果なので、

  • ${}_{n}C_{k+1}={}_{n}C_{k}\times\frac{n-k}{k+1}$

の漸化式により各項を求めていきます。

硬貨/札の枚数は、1の位~100の位に関しては同じロジックなのでまとめて行いますが、1000の位~は少し異なるので別にしています。 短く詰め込みむことを心がけましたが、やや無理やり感がありました。

終わりに

結構解いていない問題が溜まっていたので、あまり深く検討してません…。