[백준 14916] 거스름돈 (C++)

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

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

---

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

 

출력

---

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

문제 풀이

---

브루트포스 문제.

 

n이 100,000이고 2원짜리와 5원짜리밖에 없으므로 브루트포스로 해결할 수 있다. 5원짜리로 최대한 많이 변환해야 전체 동전 개수가 최소가 되므로 5원짜리로 최대한 변환하되, 남은 돈이 2원으로 변환할 수 있도록 2의 배수여야 한다.

5원을 만들 수 있는 최대 개수부터 5원이 0개인 경우까지 모든 경우를 찾아 남은 돈이 2로 나누어 떨어지는 첫번째 경우를 구해주면 된다. 

 

또 다른 방법으로는 dp를 이용해 해결할 수 있다. 이쪽이 정석적인 방법이지만, n의 크기가 작고 동전이 2개밖에 없으므로 브루트포스로 풀 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int N;
	cin >> N;
	int answer = -1;
	for (int i = N/5; i >=0; i --)
	{
		int last = N - i * 5;
		if (last % 2 == 0)
		{
			answer = last / 2 + i;
			break;
		}
	}
	cout << answer << "\n";
	return 0;
}