[그리디 #5] BOJ 14916 - 거스름돈

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

14916번: 거스름돈

 

접근 방법

간단한 그리디 문제이다.

5원과 2원 뿐이기 때문에 5원을 빼야하는 경우와 2원을 빼야하는 경우를 잘 생각해보자.

 

5원이 빠질 경우는 5원을 뺐을때, 나머지가 5으로 나누어떨어지거나 2로 나누어떨어지만 5원으로 결정.

 

2원이 빠질 경우는 2원을 뺐을때, 나머지가 2로 나누어 떨어지면 2원으로 결정.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int rest;
int cnt;

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

	cin >> n;
	rest = n;

	while (rest > 0) {
		if (rest-5>=0 && ((rest - 5) % 2 == 0 || (rest-5) % 5 == 0)) {
			rest -= 5;
			cnt++;
			
		}
		else if (rest - 2 >= 0 && ((rest - 2) % 2 == 0)) {
			rest -= 2;
			cnt++;
		
		}
		else {
			cout << -1;
			exit(0);
		}
	}
	cout << cnt;
}