[C++] 백준 5585: 거스름돈

문제

[C++] 백준 5585: 거스름돈 BRONZE 2
https://www.acmicpc.net/problem/5585

 

---

 

접근 방법

이 문제는 1000엔을 냈을 때 거슬러 받아야 할 금액이 주어지면,
동전의 개수를 최소로 사용해 거스름돈을 만드는 문제이다.

 

사용 가능한 동전은 500, 100, 50, 10, 5, 1 엔으로 이미 큰 값부터 작은 값까지 정렬된 상태이며,
이 동전 체계에서는 그리디 알고리즘이 항상 최적해를 보장한다.

 

그래서 다음과 같은 전략을 사용했다.

1. 입력받은 금액을 1000엔에서 빼서 거스름돈(money) 을 계산한다.
2. 가장 큰 동전부터 차례대로 확인하면서,
   • 해당 동전을 최대한 많이 사용한다.
   • 남은 금액은 나머지 연산으로 갱신한다.
3. 사용한 동전의 개수를 누적해 최종 결과로 출력한다.

 

구현 시 주의할 점

• 동전 배열은 큰 값부터 순회해야 최소 개수가 보장된다.

 

---

 

코드

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int money = 0;
	cin >> money;
	money = 1000 - money;  // 거스름돈

	int arr[6] = { 500, 100, 50, 10, 5,1 };
	int cnt = 0;
	for (int i = 0; i < 6; i++)
	{
		int t = 0;
		if (money >= arr[i])
		{
			t = money / arr[i];
			money %= arr[i];
			cnt += t;
		}
	}
	cout << cnt;

	return 0;
}