[백준][C++] 14916 거스름돈

1. 거스름돈

14916번: 거스름돈

문제 풀이

 

간단한 그리디 문제였다.

동전이 2원, 5원 있는데 동전을 최소 개수로 주는 방법을 구하는 것이다.

 

동전을 최소 개수로 주려면, 5원을 잘 이용해야 했다.

따라서 5의 배수가 될 때까지 전체 금액을 2원으로 빼주었다.

 

만약, 24원이라면...

 

2를 2번 빼서 5의 배수인 20으로 만들고 5를 모두 빼는 것이다.

 

#include <iostream>
using namespace std;

int main()
{
	int change;
	int count = 0;
	cin >> change;
	
    // 5의 배수가 될 때까지 2로 빼준다
	while (change % 5 != 0 && change >= 2)
	{
		change -= 2;
		count++;
	}
    
    // 5의 배수가 됐다면
    // count를 (남은 돈 / 5)만큼 올려주고 남은돈을 0으로 만든다.
    if(change % 5 == 0)
    {
        count += change / 5;
        change = 0;
    }

	// 돈을 모두 거슬러 주지 못했다면 실패
	if (change > 0 || count == 0)
		cout << -1;
	else
		cout << count;
}

이러한 로직을 짰다.

13이 거스름돈이라고 하면 순서대로 2, 2, 2, 2, 5!

20이면 5, 5, 5, 5!