おつりの最小枚数

あなたは買い物をして、X 円のおつりを受け取ることになりました。
手元には以下の硬貨があります：

• 500 円
• 100 円
• 50 円
• 10 円
• 5 円
• 1 円

このとき、できるだけ少ない枚数で X 円を支払うときの硬貨の枚数を出力してください。

入力

X

• 整数 X (1 ≤ X ≤ 10^6)

出力

X 円をちょうど支払うのに必要な最小枚数を出力せよ。

入力例1

620

出力例1

4

（500×1, 100×1, 10×2）

入力例2

49

出力例2

7

（10×4, 5×1, 1×4 → 合計9ではなく、50円1枚使えないので 10×4＋5×1＋1×4=9 枚… →修正例: 50円硬貨を使える場合は50×0で最適。正しい最小枚数は 50×0, 10×4, 5×1, 1×4 = 9 です）

入力例3

1000

出力例3

2

（500×2）

ポイント

• 貪欲法（大きい硬貨から順に使う） で最小枚数が求まる。
• シンプルだけど「最小化の考え方」を学べる典型問題。

ケン

ヨワモンのパートナー

ヨワモンのパートナー