CodeIQ過去問集35：小銭王子

本稿はCodeIQで2016年7月12日～2018年4月25日に出題された 【実力判定：Aランク】小銭王子 という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

小銭王子

【問題】

小銭をたくさん持っている小銭王子は、小銭を使った支払いに興味を持ちました。 指定された金額になる小銭の出し方のすべてのパターンを調べ、王子に教えてあげてください。 例えば、10円を支払うとき、「10円玉1枚」「5円玉2枚」「5円玉1枚と1円玉5枚」「1円玉10枚」の4通りあります。 ※小銭は500円・100円・50円・10円・5円・1円硬貨です。また、小銭王子はそれぞれの硬貨を1000枚ずつ持っています。

【入力】

標準入力から、整数値N（1≦N≦1000）が与えられます。

【出力】

合計金額がN円になる硬貨の出し方のすべての組み合わせを求め、そのパターン数を、標準出力に出力してください。

【入出力サンプル】

Input

10

Output

4

【解答方法】

[kozeni.zip]をダウンロードし、展開してください。中には以下のフォルダが含まれています。

• input: テストデータです
• output: 解答データです

テストデータを入力として、解答データと一致する出力になるようなプログラムを書いてください。

（解説は後日）