백준 - 5585 거스름돈

문제

거스듬돈의 개수가 가장 적게 잔돈을 주는 방법은?

생각

큰 단위 동전으로 거스러줄 수 있는 만큼 거슬러주자~
그때 그때 최선을 다해서 거슬러주는ㄴ거지

항상 그리디로 거스름돈 문제가 풀리는 건 아닌데
ex) 800원 400원짜리 두 개 or 500원짜리 하나 100원짜리 3개
풀릴 때가 있어

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int coin[6] = { 500, 100, 50, 10, 5, 1 };

int main() {
	int money, result = 0;
	cin >> money;
	money = 1000 - money;

	for (int i = 0; i < 6; i++) {
		if (money / coin[i]) {
			result += money / coin[i];
			money = money % coin[i];
		}
	}

	cout << result;

	return 0;
}