문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입력/출력

코드1

#include <iostream>

using namespace std;

int main() {
	int n, kg, quotient, remainder, ans = 0;

	scanf("%d", &n);

	while (n) {
		if ( n / 3 == 0  || n == 4) { // 정확하게 N키로를 맞출 수 없는 경우
			ans = -1;
			break;
		}

		quotient = n / 5;
		remainder = n % 5;
        
		if ( quotient == 0 && n % 3 == 0 ) // 5kg로 나눌 수 없지만 3kg으로 나눠지는 경우
			kg = 3;
		else if (quotient != 0 && remainder % 3 == 0) // 현재 5키로로 나눌 수 있고, 남은 무게는 3kg으로 나눠떨어지는 경우 
			kg = 5;
		else if (quotient == 2 && n % 3 == 0) // 특수한 경우를 위함 eg) 12kg
			kg = 3;
		else if (quotient >= 2 && remainder % 3 != 0) { // 5kg으로 나눠지나, 남은 무게가 3kg으로 나눠지지 않는 경우
			ans++;
			n -= 5; // 5*x무게가 아닌 5kg씩 제거
			continue;
		}
		else // 이외의 경우는 3kg로 나눠떨어지는 경우
			kg = 3;

		ans += n / kg;
		n -= (n / kg)*kg;
	}
	
	printf("%d\n", ans);

	return 0;
}

풀이1

가장 처음 생각 한 방식으로, 문제를 풀기 위해 여러가지 경우의 수를 생각해서 while문 안에 if-else문을 이용해 원래 값인 N무게를 줄여나가도록 하였다.
여러 경우의 수를 생각하다 보니 코드가 간결하지 못하다. 위와 같이 코드를 작성한 이유는 5Kg을 우선적으로 생각해 줄여나가기를 했다.

코드2

#include <iostream>

using namespace std;

int main() {
	int n, kg, quotient, remainder, ans = 0;

	scanf("%d", &n);

	while (n > 2) {
		if (n % 5 == 0) {
			ans += n / 5;
			n = 0;
			break;
		}
		n -= 3;
		ans++;
	}

	if (n) // n의 무게가 아직 남아있는 경우
		ans = -1;

	printf("%d\n", ans);

	return 0;
}

풀이2

코드를 좀 더 간결하게 만들기 위해 5kg을 우선적으로 줄이는 ‘코드1’과 다르게 반대로 생각해 보았다.
5kg으로 나눠 떨어지지 않으면 3kg씩 줄여나가는 방법을 쓰니 코드의 길이가 확 줄었다. 최소한의 봉지를 사용해야한다는 생각에 사로잡혀 무조건 큰 봉지부터 채워나가는 방식을 생각했는데, 생각의 전환이 필요한 것같다.