거스름돈 (백준 - 5585번)

동전 0 문제와 유형이 비슷한 문제이다. 그리디 알고리즘 문제이다.

입력 받은 가격을 1000엔과 빼서 나머지 거스름 돈 값을 구한다.

그리고 500엔부터 차례대로 거스름돈 보다 가치가 적거나 같은 경우 그 가치에 맞는 동전 개수를 구한 후 최종 값에 더해주고, 거스름돈에서 구한 만큼의 가치를 빼주면 된다.

이 작업을 동전 가치가 1엔이 될때까지 혹은 거스름돈이 0엔이 될때까지 반복해주면 된다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	int maxMoney = 1000;
	int coinArr[6] = { 500, 100, 50, 10, 5, 1 };
	int change = 0;
	int changeCoinCount = 0;

	int price = 0;

	cin >> price;

	change = maxMoney - price;

	for (int i = 0; i < 6; ++i)
	{
		if (change <= 0)
			break;

		if (change >= coinArr[i])
		{
			changeCoinCount += change / coinArr[i];
			change = change % coinArr[i];
		}
	}

	cout << changeCoinCount << endl;
}