[BOJ/백준] 2839번 설탕 배달 C++ 문제 풀이

단계별로 풀어보기 - 수학 1 단계 - [2단계] 2839번

문제

문제 링크 : www.acmicpc.net/problem/2839

2839번: 설탕 배달

입력 복사 : 

> 예제 입력 1

18

> 예제 입력 2

4

> 예제 입력 3

6

> 예제 입력 4

9

> 예제 입력 5

11

 

풀이

최소의 봉지로 배달하기 위해서는 5kg짜리 봉지를 최대한 활용해야 한다.

따라서 5kg짜리 봉지를 최대로 활용하는 횟수를 시작으로 한다.

 

5kg를 활용한 횟수를 뺀 N이 3kg으로 나눠지면, 바로 정답을 출력합니다.

나누어 떨어지지 않으면,

5kg으로 나눈 횟수를 줄이고 3kg으로 나눈 횟수를 늘리는 과정을 3kg으로 나누어 떨어질 때까지 반복합니다.

 

하지만 반복이 계속되어 5kg으로 나눈 횟수가 음수가 된다면,

-1을 출력하고 return하여 종료합니다.

 

CODE

#include <iostream>
using namespace std;

int main() {
	int N;
	int div_five, div_three;	//5, 3으로 배달한 횟수를 저장할 변수
	cin >> N;

	div_five = N / 5;
	while (1) {
		if (div_five < 0) {
			cout << -1 << endl;
			return 0;
		}
		if ((N - (5 * div_five)) % 3 == 0) {
			div_three = (N - (5 * div_five)) / 3;
			break;
		}
		div_five--;
	}
	cout << div_five + div_three << endl;
	return 0;
}

 

결과