백준 5585번(그리디)

백준 5585번(그리디)

이 문제는 정말 유명한 거스름돈 동전 갯수 문제입니다. 물론 알고리즘을 많이 풀어보지는 않았지만 거스름돈 유형은 정말 많이 들어봤던 것 같습니다. 문제 자체는 어렵지 않았습니다. 기본 주어진 금액 1000에서 입력으로 받은 값을 뺀 뒤 그 값을 동전들과 내림차순으로 비교해나갔습니다. 그리고 금액이 동전보다 클경우 그 동전의 금액으로 나눠서 동전 갯수를 더해주고, 나머지를 구하는 연산을 반복했습니다.

#include <iostream>

using namespace std;

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

int main() {
	int money;
	int change;
	int result = 0;

	cin >> money;

	change = 1000 - money;

	for (auto& coin : coinArr) {
		if (coin <= change) {
			result += change / coin;
			change %= coin;
		}
	}

	cout << result;

	return 0;
}