[BaekJoon][Greedy] 5585. 거스름돈

/* 문제 : [5585] 거스름돈
[input]
380
[output]
4
[설명]
지불할 돈(1~999)을 내고 1000엔 지폐를 한 장 내면 500, 100, 50, 10, 5, 1엔으로
가장 적게 잔돈을 주기 위한 동전의 개수를 출력해라.
*/
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v = { 500, 100, 50, 10, 5, 1 };
	int money;			// 거스름돈
	int price;			// 지불할 돈
	int count = 0;		// 동전 개수

	cin >> price;
	money = 1000 - price;

	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		count += money / v[i];
		money %= v[i];

		if (money == 0) {
			cout << count;
			break;
		}
	}

	return 0;
}