[백준/BOJ] 백준 5585번 : 거스름돈

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

그리디 알고리즘을 통해 문제를 해결하였다.

잔돈을 가장 적게 주려면, 가능한 금액이 큰 동전을 돌려줘야 한다. 이 코드에서는 point변수를 이용해 남은 잔돈에 대해 가능한 큰 금액의 동전을 구하였다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

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

	vector<int> coin;
	int pay;
	int result;
	int point = 0;
	int cnt = 0;

	//동전을 내림차순으로 정리한다.
	coin.push_back(500);
	coin.push_back(100);
	coin.push_back(50);
	coin.push_back(10);
	coin.push_back(5);
	coin.push_back(1);

	cin >> pay;

	result = 1000 - pay;
	
	//더이상 잔돈이 없을때 종료
	while (result != 0)
	{
		//잔돈이 point지점의 동전보다 작다면 더 작은 동전 선택을 위해
		//point지점을 한칸 옮긴다
		if (result < coin[point] && (point+1 < 6) )
			point++;
		else 
		{
			result -= coin[point];
			cnt++; //개수 추가
		}
	}

	cout << cnt;

	return 0;
}