거스름돈

문제

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

해당 문제는 입력으로 주어진 금액을 5원, 2원짜리 동전을 최소로 사용하여 거슬러 주는 문제이다.

해당 문제를 해결하기 위해 그리디 알고리즘을 활용하여 접근했다.
이를 위해 입력으로 주어진 금액을 가장 빠르게 줄이기 위해 5원으로 거슬러 주는 과정을 최우선순위로 생각했다.

하지만 그리디 알고리즘을 활용할 때 주의점은 그리디 접근을 위해 고려한 선택지가 최적의 선택을 보장할 수 있는지에 대한 선택지 사이에서 정당성 확인이 필요하다.

1)

이를 고려하면, 입력으로 주어진 금액을 단순히 5원으로 거스르고 나머지 금액을 2원으로 거슬러 주는 과정은
5원으로 나누었을때 나머지 금액이 홀수인 경우에는 2원으로 거슬러 줄 수 없는 문제가 발생했다.

따라서 이러한 경우, (5원으로 거스른 몫 - 1) 만큼만 5원으로 거스르고 나머지 금액은 2원으로 거슬러 줘야 입력 금액을 거슬러 줄 수 있다.

2)

1번에서 연장선 상으로 2원과 5원짜리 동전으로 거슬러 줄 수 있는 금액의 범위를 고려한다.
2원과 5원짜리 동전으로 거슬러 줄 수 없는 금액은 5원 보다 작은 홀수인 3원이 입력된 경우이다.

따라서 입력 금액으로 3원이 입력된 경우, 문제의 조건에 따라 예외처리를 해줘야 한다.

이를 고려한 전체 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);

	int n, temp, cnt, res;

	cin >> n;

	temp = n;
	res = 0;
	cnt = 0;

	if (temp % 2 == 1 && temp < 5) {
		cout << "-1" << "\n";
		return 0;
	}

	if ((temp % 5) % 2 != 0) {
		cnt = (temp / 5) - 1;
		res += cnt;
		temp -= cnt * 5;
	}

	else {
		cnt = temp / 5;
		res += cnt;
		temp -= cnt * 5;
	}

	cnt = temp / 2;
	res += cnt;
	temp -= cnt * 2;

	if (res == 0) {
		cout << "-1" << "\n";
	}

	else {
		cout << res << "\n";
	}
	
	return 0;
}