BOJ 14916 거스름돈

동전의 갯수가 최소가 되기 위해 5원짜리를 최대한 많이 사용하여 거슬러주면된다. 하지만 여기서 핵심은 무조건 5원짜리를 가자 많이 사용한다고 최대가 되지 않는다. 예를들어 13원일 경우 5원 2개로 거슬러주면 나머지 3원은 2원 짜리로 거슬러 줄 수 없다. 따라서 5원 1개 2원 4개 총 5개의 동전이 최소가 된다.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

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

	int n;

	cin >> n;

	int result = 99999999;

	for(int i = 0; i <= (int)floor(n / 5); i++)
	{
		int money = n - (i * 5);
		if(money % 2 == 0)
		{
			result = min(result, i + (money / 2));
		}
	}

	if(result > n)
	{
		cout << -1;
	}
	else
	{
		cout << result;
	}
}