CodeIQ 挑戦の記録 : 第74回「今週のお題：枚数で考えるパスカルの三角形」
- CodeIQというサイトで問題に挑戦した記録です。
- 気が向いたら不定期に更新します。
第74回「今週のお題：枚数で考えるパスカルの三角形」
- 問題文を引用します。
今週のお題：枚数で考えるパスカルの三角形より、
問題文のページは現在リンク切れ
規則性を学ぶ上でよく登場する「パスカルの三角形」。
各行の左右の端を「1」、それ以外の箇所は左上と右上の数の和を書くことで作成できます。今回は、それぞれの値を「金額(日本円)」だと考えることにします。
例えば、「1」は1円、「2」は2円、「10」は10円です。
このとき、n段目のそれぞれの値について、お札や硬貨での最小の枚数を考え、その枚数の和を求めることにします。
例えば、n=4のとき、1, 4, 6, 4, 1の並びでは、1円＝1枚、4円＝4枚、6円＝2枚(5円玉＋1円玉)なので、 すべて足すと12枚になります。
同様に、n=9のとき、すべて足すと48枚になります。標準入力からnの値が与えられたとき、その枚数の和を標準出力に出力するプログラムを作成してください。
なお、使える硬貨、お札は1円玉、5円玉、10円玉、50円玉、100円玉、500円玉、1000円札、2000円札、5000円札、10000円札です。
（※nの値は最大で50までとします。）
今回は以下の2点をポイントに素直に実装した。
パスカルの三角形
今回、パスカルの三角形の第n段目のそれぞれの値を求める必要があるが、
nの最大が50なので、定義に従い、パスカルの三角形を実際に作成して求めても1秒の時間制限に十分間に合うでしょう。（やってない）
しかし、それぞれの値は二項展開における係数そのものなので、二項係数を直接求める事にする。
二項係数とはつまり、高校の数学で習った、n個のものからk個のものを選ぶ組み合わせに等しい
は
で計算できる。
これをそのまま実装するのは難しくないが、計算順序がマズイとすぐにオーバーフローしてしまう。
過去に相当程度大きいnでもオーバーフローしない二項係数を求める汎用的な関数を書いたが、あまりにアレな実装だったので今回ググって、下記のページを参考とさせて頂き、実装した。
ある金額を最小の枚数で構成する紙幣・硬貨の組み合わせの求め方
貪欲法というアルゴリズムで解ける典型問題である。
日常的にも、何か支払いをする時に、最も大きい金額の紙幣・硬貨から支払い金額を越えない様に選べるだけ選ぶという方法をとる事は自然な事と思う。正にこの方法を実装すれば良い。
（但し、現実に日本で発行されている紙幣・硬貨のセットであれば貪欲法で問題ないが、
仮に「8円硬貨」があるとする問題では貪欲法で最適解を求められない。
例:16円を選ぶ場合）
以下は提出したコード(Ruby)
