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

 

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

14916번: 거스름돈

 

 

문제

정수 n(1<=n<=100,000) 이 주어질 떄, 2원과 5원으로 조합할 수 있는 동전의 최소 개수를 출력한다. 불가능할 경우 -1을 출력한다.

 

풀이

2원짜리가 있기 때문에 남은 거스름돈이 짝수일 경우, 거스름돈 조합을 만드는 것이 무조건 가능하다. 5원으로 만들 수 있는 금액을 다르게 하며 가능한 모든 경우를 계산한다.

#include <iostream>
using namespace std;


int n, cur = 0, ans = 999999;

int main() {
	cin >> n;

	// 짝수면 가능
	// 5를 더해가면서 확인

	while (cur <= n) {
		if ((n - cur) % 2 == 0) {
			ans = min(ans, cur / 5 + (n - cur) / 2);
		}
		cur += 5;
	}

	if (ans == 999999) cout << -1;
	else cout << ans;
}