081 - Bill Changing Problem
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
1000 円札、5000 円札、10000 円札を使って N 円を支払いたいです。最小何枚で支払うことが出来るか求めてください。
ただし、紙幣はどれも十分にあるものとします。
制約
- 1000 \le N \le 200000
- N は 1000 の倍数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
N 円払うための最小の枚数を出力してください。
入力例 1
29000
出力例 1
7
10000 円札 2 枚、5000 円札 1 枚、1000 円札 4 枚を使うと、7 枚の紙幣で支払うことができます。