「今週のお題：枚数で考えるパスカルの三角形」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
入力 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の位～は少し異なるので別にしています。 短く詰め込みむことを心がけましたが、やや無理やり感がありました。
終わりに
結構解いていない問題が溜まっていたので、あまり深く検討してません…。
