그리디_거스름돈

추론

• 핵심.
  가장 큰 단위에서 작은 단위로 나눌 경우를 생각했을 때 문제가 없음.
  but 800원인데 500, 400 , 100 일 경우 문제다.
  -> 가장 큰 단위의 수가 작은 단위의 값들의 배수이기 때문에 가능한 문제임.
  현재 500, 100, 50, 10 이므로 단위로 처리가 가능함.
  그러나 500, 400, 100 의 경우는 다르게 접근해야 함.

코드

#include <stdio.h>
using namespace std;
#include <iostream>
#include <typeinfo>



int main()
{
	cout << "얼마의 돈을 갖고 있나요?? 10원 단위로 입력 하라" << endl;
	int input;
	cin >> input;

	// 500, 100 , 50 , 10 
	int arr[]{ 500,100,50,10 };
	int cnt = 0;

	// 가장 큰 거부터 처리해 나감.
	for (auto money : arr)
	{
		// 800 원이면... 
		// 400 원이면... 
		// => 대소 비교를 해야함. 
		if (input >= money)
		{
			int mock = input / money;
			input -= mock * money;
			cnt += mock;
			cout << money << "원으로 " << mock << " 개 사용함. " << endl;

		}

		if (input <= 0)
		{
			cout << "탈출" << endl;
			break;
		}
		// 작을 때는 아예 진행 안함.

	}

	cout << "사용한 동전의 총 갯수는 " << cnt << "개 입니다." << endl;
}