[백준 10757번][C++] 백준 설탕 배달

www.acmicpc.net/problem/2839

2839번: 설탕 배달

문제

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

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

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

입력

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

출력

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

---

풀이

Algorithm

1. 배달해야하는 설탕 Nkg을 5로 나눈 몫과 나머지로 문제를 해결할 수 있어요!
   • N = 5*q+r 이라고 합시다
   • r이 될 수 있는 수는 0, 1, 2, 3, 4이겠죠?
   • 나머지(r)가 0일 때 N = 5*q이므로 총 필요한 봉지 수는 5kg짜리 봉지 수 그대로 q가 될 것입니다
   • 나머지(r)가 1일 때 N = 5*q+1 = 5*(q-1)+5+1 = 5*(q-1)+6에서 6kg은 3kg짜리 봉지 두 개로 나눠가져갈 수 있으므로 총 필요한 봉지 수는 (5kg짜리 q-1개) + (3kg짜리 2개) = q+1개 입니다
   • 나머지(r)가 2일 때 N = 5*q+2 = 5*(q-2)+10+2 = 5*(q-2)+12에서 12kg은 3kg짜리 봉지 네 개로 나눠가져갈 수 있으므로 총 필요한 봉지 수는 (5kg짜리 q-2개) + (3kg짜리 4개) = q+2개 입니다
   • 나머지(r)가 3일 때 N = 5*q+3에서 5kg짜리 봉지 q개로 담고 남은 3kg은 3kg짜리 봉지 한 개에 담아 가져갈 수 있으므로 총 필요한 봉지 수는 (5kg짜리 q개) + (3kg짜리 1개) = q+1개 입니다
   • 나머지(r)가 4일 때 N = 5*q+4 = 5*(q-1)+9에서 5kg짜리 봉지 q-1개로 담고 남은 9kg은 3kg짜리 봉지 3개로 나눠가져갈 수 있으므로 총 필요한 봉지 수는 (5kg짜리 q-1개) + (3kg짜리 3개) = q+2개 입니다
   • 설명이 복잡하므로, 아래에 도표로 간단하게 나타내었어요!
2. 이에 따라 코드로 표현해줘요
   • switch문으로 r이 0일땐 q를, 1또는 3일땐 q+1을, 2또는 4일땐 q+2를 출력해요
3. 예외 처리를 해줘요
   • 문제에서 N의 조건은 3이상이고 5000이하라는 것이에요
   • 예외는 r이 1이고 q가 1보다 작을 때, 또는 r이 2이고 q가 2보다 작을 때, 또는 r이 4이고 q가 1보다 작을 때예요.
   • 잘 찾아보면 위 두 조건을 만족하는 만들 수 없는 N은 4와 7밖에 없어요!
4. 이를 코드로 나타내주면 끝!

나머지(r)	5kg짜리 봉지 (개)	3kg짜리 봉지 (개)	총 필요한 봉지 (개)
0	q	0	q
1	q-1	2	q+1
2	q-2	4	q+2
3	q	1	q+1
4	q-1	3	q+2

 

code

#include <iostream>
using namespace std;

int main() {
	int N, q, r;
	cin >> N;
	if (N == 4 || N == 7)
		cout << -1 << endl;
	else {
		r = N % 5;
		q = N / 5;
		switch (r) {
		case 0:
			cout << q << endl;
			break;
		case 1:
		case 3:
			cout << q + 1 << endl;
			break;
		default:
			cout << q + 2 << endl;
			break;
		}
	}
	return 0;
}