[백준] 5585번 거스름돈

#include<iostream>

using namespace std;

int main() {

	int n;
	cin >> n;
	n = 1000 - n;
	int result = 0;
	result += n / 500;
	n %= 500;
	result += n / 100;
	n %= 100;
	result += n / 50;
	n %= 50;
	result += n / 10;
	n %= 10;
	result += n / 5;
	n %= 5;
	result += n / 1;

	cout << result << endl;

	return 0;
}

포인트 : 그리디 알고리즘을 이용한다. 나눈 값을 더해주어 갯수 체크하고, %를 이용하여 나머지를 나타낸다.