그리디 알고리즘(Greedy Algorithm).

/*
그리디 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘.
항상은 아니지만, 어느정도는 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있음.
특정한 상황에서는 그리디 알고리즘이 최적의 해를 보장할 수도 있음.

그리디 알고리즘의 대표적인 예는 거스름 돈 문제.
가장 적은 양의 화폐를 주는 것이 편하므로, 무조건 더 큰 화폐 단위부터 거슬러 준다는
알고리즘만 지키면 최적의 해를 보장.

이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 
무조건 긴 경우대로 등 극단적으로 문제에 접근 한다는 점에서 정렬(sort)기법이 함께 
사용되는 경우가 많음. 대표적인 예시로 크루스칼 알고리즘.(모든 간선을 정렬한 이후,
짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘)
*/

#include<iostream>

using namespace std;

int main()
{
	int n, result = 0;
	cin >> n;

	result += n / 500;
	n %= 500;

	result += n / 100;
	n %= 100;

	result += n / 50;
	n %= 50;

	result += n / 10;

	cout << result;

	return 0;
}