[백준] 5585번 거스름돈

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

greedy 알고리즘의 아주 대표적인 문제이다.

#include <iostream>
using namespace std;

int main() {
	int cost;
	cin >> cost;
	int money[] = { 500, 100, 50, 10, 5, 1 };
	int change = 1000 - cost;
	int total = 0;
	int cnt = 0;
	while (true) {
		if (change == total) break;
		if (total + money[0] <= change) {
			total += money[0];
			cnt++;
		}
		else if (total + money[1] <= change) {
			total += money[1];
			cnt++;
		}
		else if (total + money[2] <= change) {
			total += money[2];
			cnt++;
		}
		else if(total + money[3] <= change) {
			total += money[3];
			cnt++;
		}
		else if (total + money[4] <= change) {
			total += money[4];
			cnt++;
		}
		else if (total + money[5] <= change) {
			total += money[5];
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}