wizardrabbit   3년 전

* 본 지문은 26934번 문제를 번역하여 작성하였으며, 문제의 이해를 돕기 위해 일부 의역이나 새로운 내용이 포함되어 있을 수 있습니다.

문제

당신은 버스를 타기 위해 요금을 지불하려고 한다. 카드를 깜빡하고 가지고 나오지 않았기 때문에, $100$ 원, $200$ 원, $500$ 원 짜리 동전만을 이용하여 지불하려고 한다. 지불은 아래와 같은 방법으로 할 예정이다.

  1. 버스 요금보다 지불 금액이 같거나 더 많도록 지불하면서, 가능한 한 지불 금액을 최소로 한다.
  2. 1. 에서 정한 지불 금액을 최소한의 개수의 동전을 사용하여 지불한다.

예를 들어 버스 요금이 $850$ 원일 경우 $900$ 원을 지불하는 것이 지불 금액을 최소로 할 수 있는 금액이고, $900 = 500 + 200 + 200$ 으로 사용하는 동전의 개수를 최소화했을 때의 동전의 개수는 $3$ 이 된다.

위의 방법대로 버스 요금을 지불할 때, 사용하는 동전 개수의 최솟값을 출력하시오. 가지고 있는 세 동전의 개수는 무한하다고 가정하자.

입력

첫 번째 줄에 지불해야 하는 버스 요금 $K$ 가 원 단위로 주어진다.

출력

첫 번째 줄에 문제에서 제시한 방법대로 버스 요금을 지불할 때, 사용하는 동전 개수의 최솟값을 출력한다.

제한

  • $1 \le K \le 10\;000$
  • $K$ 는 정수

댓글을 작성하려면 로그인해야 합니다.