[BAEKJOON] 2839번 : 설탕 배달

문제

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

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

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

입력

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

출력

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

예제 입력 1

18

예제 출력 1

4

예제 입력 2

4

예제 출력 2

-1

예제 입력 3

6

예제 출력 3

2

예제 입력 4

9

예제 출력 4

3

예제 입력 5

11

예제 출력 5

3

 

---

풀이

처음 생각했을때는 N>=5일때 N-=5를 하자는 단순한 생각으로 풀었다. 하지만 3, 6, 9 ,12와 같이 5 없이 3으로만 계산되는 수들을 생각하지 못했다는것을 뒤늦게 알았다.

 

5와 3의 공배수를 기준으로 생각하다가 자꾸 머리가 꼬여서 숫자를 나열하고 규칙을 무대뽀로 찾아보고자했다.

경우의 수들

1. N과 3 사이의 관계

(N % 3)이 0, 1, 2의 주기를 가진다는 점을 중심으로 나누어 보았다.

N과 3의 관계

14까지 봤을 때는 (N % 3)의 값이 0, 2일 때 Count가 같은 수가 나오고 (N % 3) 이 1일 때 다른 수를 나타냄을 알 수 있었다.

- (N % 3) 이 0, 2일 때 1, 2, 3, 4, 5 ...로 N/3과 Count가 같은 수를 나타낸다.

- (N % 3) 이 1일 때 Count는 위 경우보다 1 낮은 수가 나온다.

 

그러나 15가 등장하면서 위 이론이 깨졌다.. 이후로 규칙을 다시 재정립하려다 머리가 꼬여서 N과 5 사이의 관계로 넘어갔다.

 

2. N과 5 사이의 관계

(N % 5)가 0, 1, 2, 3, 4의 주기를 가진다는 점을 중심으로 나누어 보았다.

N과 5의 관계

쭉 살펴본 결과 세 가지로 규칙이 나뉨을 볼 수 있었다.

 

- (N % 5)가 1, 3 일 때 Count = (N / 5) + 1

- (N % 5)가 2, 4 일 때 Count = (N / 5) + 2

- (N % 5)가 0 일 때 Count = (N / 5) 

라는 규칙이 나온다.

코드

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;

	if (n == 4 || n == 7) {
		cout << -1;
		return 0;
	}

	if (n % 5 == 1 || n % 5 == 3) {
		cout << n / 5 + 1;
	}
	else if (n % 5 == 2 || n % 5 == 4) {
		cout << n / 5 + 2;

	}
	else {
		cout << n / 5;
	}

}