알고리즘문제 14916 풀이

문제

춘향이는 편의점 카운터에서 일한다.손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.
예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

핵심

문제의 핵심은 우리가 거슬려 줘야하는 동전의 개수가 최소가 되도록 해야하는 것이다. 동전 개수를 최소로 하기 위해서는 어떻게 해야할까? 바로 거스름돈을 가장 큰 액수의 동전을 가장 많이 채운 다음 못 채운 나머지 거스름돈을 그보다 작은 액수의 동전들로 채우는 것이다.

이제 문제를 보도록 하자. 문제에서는 거스름돈을 n이라고 주어졌다. 그리고 우리는 거스름돈을 손님이 요구하는 대로 2원짜리 동전과 5원짜리 동전으로만 거슬러 줘야한다. 우리에게는 무한개의 2원, 5원동전이 있으므로 얼마를 거슬러 주든 한가지 동전으로만 거슬러 줄 수도 있다. 하지만, 거슬러주는 동전 개수를 최소화해야하므로 위의 방법으로 5원짜리 동전으로 가장 많이 채운다음 나머지 거스름돈을 2원짜리로 채울 것이다.

이를 수식으로 표현해보자.

그럼 n은 거스름돈이 되고, x는 5원짜리 동전의 개수 y는 2원짜리 동전의 개수가 될것이다.

수식: n=5x+2y 이다. 여기서 우리는 거스름돈을 5원짜리으로 많이 채울수록 좋다. 즉, 가장 좋은 경우 거스름돈 n을 5원짜리로만 거슬러 주는 것이다. 이 경우 우리는 n이 5로 나누어 떨어진다고 할 수 있다. 즉, n % 5 =0 (이떄 %은 나머지를 구하는 기호)으로 표현하고, n을 5로 나누었을때 나머지가 0이라는 의미라고 한다.

하지만, n이 꼭 5으로 나누어떨어진다고 할 수 없다. 이때, 우리는 나머지 거스름돈을 2원으로 채워야 한다. 이를 다시 표현하면, n을 5으로 나누었을때 나머지가 0이 아닌, 1~4 중 하나가 나오는 것이다. 그렇다면, 거스름 돈 n을 5원으로 채운 다음 2원으로 채워야 하는데, 나머지가 2,4일때는 2원으로 채우면 될 것이다. 하지만, 나머지가 1혹은 3인경우 2원짜리 동전으로 채울 수가 없다. 그러면 우리는 5원짜리 동전을 하나씩 덜 거슬러 줘서, 나머지 돈을 2원짜리로 다 채울 수 있도록 해줘야하는 것이다. 이 원리를 적용해서 문제를 풀자.

		#include<iostream>
		using namespace std;
		int main()
		{
			int n, x, y;
			cin >> n;
			x = n / 5 ; //우리가 거슬러 줘야하는 동전의 개수
			y = 0;
			while(((n - 5 * x) % 2) != 0) { // 나머지를 2으로 나누어서 0으로 떨어지면 while문을 탈출, 아니면(나머지가 1혹은 3이면) x를 감소하고 다시 계산
				if (x == 0) {  //문제가 n=1,3, 등등 안 나누어 떨어지는 경우가 생기면 x가 0이될때까지 while문을 돌것이다. 이 경우 앞의 while 조건식에서 조건식을 만족하여 if 문으로 진입한것이므로, 5원짜리 동전으로 몇개를 빼든 2원짜리 동전으로 채울 수 없다. 즉, 거스름돈을 거슬러 줄 수 있는 방법이 없는것 -> 종료하는 것이 맞다.
					printf("-1");
					return 0;  
				}
				x--;
			}
			y = (n - 5 * x) / 2;  
			printf("%d", x + y);		
		}

조건문은 나머지를 2으로 나누어서 0으로 떨어지면 while문을 탈출, 아니면(나머지가 1혹은 3이면) x를 감소하고 다시 계산하도록 반복문을 설정하였다. 다음에는 안에서 만약 거스름돈 n이 5원 혹은 2원으로도 나누어 떨어지지 않는 숫자라면, -1을 출력하고 강제종료하도록 하였다.
위의 루프를 걸친후 while문을 탈출하게 되면 거스름돈 n이 5원과 2원으로 나누어떨어지는 수라는 의미이다. (while문 내의 조건에서 설정함) 그러므로, x값을 통해 y값을 구할수 있으며, x+y 값을 구할 수 있게 된다.

n=1을 입력했을때

n=2을 입력했을때

느낀점

개인적으로 이 문제를 풀면서 닥쳤던 문제점은 2가지가 있다.
1. while문을 거치는 거스름돈 n이 나누어 떨어지는 수가 아닐때의 조건 설정 -> x==0 일때 더이상 5원으로 나누어 떨어지지 않으며, 앞의 while문을 통해서 2으로도 나누어 떨어지지 않는다는것을 확인, -1을 출력
2. while문 안에서의 break이외의 해결법을 탐색하는 것 (while문안에서 if문을 설정하다보니, break만으로는 최대 while문까지밖에 탈출하지 못함. 그래서 문제가 요구하는 대로 -1을 출력후 x+y값이 여전히 출력됐음) -> -1을 출력하고, break 대신 return 0 라는 전체 프로그램 종료명령을 사용. 그러면 코드가 if문에 진입하면, -1을 출력 후 return 0을 만나서 이후로 진행되지 않고 종료되게 된다.