[C++] 2839 설탕 배달

---

 

나누기, 나머지 연산을 이용하는 문제

​

머리가 굳어버려 쩔쩔매던 중에 힌트 발견해서 단번에 성공.

(감이 안 잡힐 때에는 저 힌트를 보자.)

​

문제는 설탕 N kg을 배달하는데, 봉지의 갯수를 최소한으로 해야한다는 것.

결국 5kg 짜리 봉지를 가능한 한 많이 끼워넣고 시작해야한다.

​

그럼 먼저, N(3 이상)을 5로 나눈 나머지를 구해보자.

3, 4, 0, 1, 2 가 반복된다.

그렇다는 얘기는 N%5의 결과에 따라 경우가 나뉜다는 뜻.

경우에 따라 구분하여, 각각의 규칙을 찾아본다.

​

if (N%5 == 3):

5로 나눴을 때의 나머지가 3인 숫자는

3, 8, 13, 18, 23, ...

3을 제외하고 8부터는 5x + 3의 꼴이다.

​

if (N%5 == 4):

4, 9, 14, 19, 24, ...

4는 3과 5로 나타낼 수 없다.

9는 3*3

14부터는 5x + 9 의 형태가 계속된다.

​

if (N%5 == 0):

5, 10, 15, 20, 25, ...

5개짜리로 모두 배달 가능함이 자명하다.

​

if (N%5 == 1):

6, 11, 16, 21, 26, ...

6은 3*2

11부터는 5x + 6 의 형태가 계속된다.

​

if (N%5 == 2):

7, 12, 17, 22, 27, ...

7 또한 3과 5로 표현 불가능.

12는 3*4

17부터는 5x + 12

 

#include <iostream>

using namespace std;

int HowManyBags(int n)
{
	int remainder(n % 5);

	switch (remainder)
	{
	case 3:
		cout << (n / 5 + 1) << endl;
		break;

	case 4:
		if (n / 5 == 0) cout << -1 << endl;
		if (n / 5 == 1) cout << 3 << endl;
		if (n / 5 > 1) cout << (n / 5 - 1) + 3 << endl;
		break;

	case 0:
		cout << n / 5 << endl;
		break;

	case 1:
		cout << (n / 5 - 1) + 2 << endl;
		break;

	case 2:
		if (n / 5 == 1) cout << -1 << endl;
		if (n / 5 == 2) cout << 4 << endl;
		if (n / 5 > 2) cout << (n / 5 - 2) + 4 << endl;
		break;
	}

	return 0;
}

int main()
{
	int N;
	cin >> N;
	HowManyBags(N);
}