The Bus Card

면접 대비

시간 제한1초메모리 제한1024 MB

요약

목표 금액 K가 주어질 때, 100, 200, 500 SEK 충전을 합쳐 K 이상이 되도록 하는 최소 충전 횟수를 구한다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

You are going to purchase a bus card. It's a refillable card that cash can be deposited into, and then used to ride the bus until you are out of money. You know that you're planning to travel for $K$ Swedish crowns (SEK). Charging the card takes some time since you can only charge it with $100$ , $200$ or $500$ SEK at a time.

At the moment you are in a hurry, so you want to make as few transactions as possible, but never insert more money than necessary. If you are to travel for $800$ SEK, this means you should load it with $500$ , then $200$ , and then $100$ SEK. On the other hand, if you are traveling for $850$ SEK you should load it first with $500$ , and then $200$ SEK twice. $50$ SEK will be wasted, but it's still the best alternative.

Compute the minimum number of transactions necessary.

입력

The input consists of the integer $K$ ( $1 \le K \le 10\\,000$ ), the amount you will travel for.

출력

Output a single integer -- the number of transactions necessary.

예제2

예제 1
입력
```
850
```
예상 출력
```
3
```
예제 2
입력
```
1800
```
예상 출력
```
5
```