[BOJ] 5585 : 거스름돈

Question

---

Solution

그리디 알고리즘은 아주 단순하다.

• 가장큰 화폐부터 작은 화폐까지 차례로 나눈 몫을 모두 더하면 가장적은 수가 나온다.

---

Cord

#include <iostream>

using namespace std;

int main()
{
	// 지불할 비용
	int cost;
	cin >> cost;

	int change = 1000 - cost; // 받아야 할 거스름돈
	int result = 0;	// 최저 갯수

	// 최저 수 구하기
	result += change / 500;
	change = change % 500;
	result += change / 100;
	change = change % 100;
	result += change / 50;
	change = change % 50;
	result += change / 10;
	change = change % 10;
	result += change / 5;
	change = change % 5;
	result += change / 1;
	change = change % 1;

	// 출력
	cout << result;

	return 0;
}

---

Result