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

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

14916번: 거스름돈

1. 문제 설명

 

거스름돈(1 <=n <=100,000)이 입력으로 주어졌을 때, 2원 / 5원 동전으로 거슬러줄 수 있는 최소 동전의 개수를 구하는 문제

 

이런 문제는 dp로 풀 수 있지만 문제가 간단하여 수학으로 풀 수 있다.

 

5원이 2원보다 크므로 가능한 5원을 더 많이 쓰는 게 동전을 적게 쓸 수 있다.

 

거스름돈을 5원으로 나누어줄 경우 나머지는 4,3,2,1,0이다.

 

나머지가 4,2일 경우 2로 나누어질 수 있기 때문에 최소 동전의 개수는 거스름돈/5 + 거스름돈%5/2한 값이다.

 

나머지가 3,1일 경우는 2로 나누어질 수 없다. 그러므로 5원 동전을 하나 덜 사용하여 나머지를 8,6으로 만들어 2로 나눈다. 이때 최소 동전의 개수는 거스름돈/5-1+(거스름돈%5+5)/2이다.

 

나머지가 3,1일 경우 5원 동전을 하나 덜 사용한다고 가정하기 때문에 최소한 거스름돈이 5원 동전을 하나 사용할 수 있는, 즉 5원 보다 커야 한다. 5원 보다 작을 경우 거스름돈은 거슬러 줄 수 없기 때문에 -1을 출력한다.

 

 

 

 

2. 코드

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

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

	cin >> coin;

	if ((coin % 5) % 2 == 0)
		cout << coin / 5 + coin % 5 / 2 << "\n";
	else if (coin / 5 == 0)
		cout << "-1\n";
	else
		cout << coin / 5 + (coin % 5 + 5) / 2 - 1 << "\n";

	return 0;
}