[백준] 2839번: 설탕 배달

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

문제풀이

경우의 수를 크게 아래와 같이 두 가지로 나눌 수 있다.

1. 5킬로그램 봉지로 다 채워지는 경우 (5로 나눈 나머지가 0인 경우)

2. 5킬로그램 봉지에 모두 담아지지 않는 경우 (5로 나눈 나머지가 0이 아닌 경우)

5로 나눠지는 15와 같은 경우는, 그 몫을 출력하면 된다.

하지만 2번의 경우 몇가지 예를 들면,

18킬로그램

① 5킬로그램 봉지 3개 --- 3킬로그램 남음

② 3킬로그램 봉지 1개

9킬로그램

방법1

① 5킬로그램 봉지 1개 --- 4킬로그램 남음

② 3킬로그램 봉지 1개 --- 1킬로그램 남음

방법2

① 3킬로그램 봉지 3개

위 작업 순서를 간단히 적어보면 아래와 같다.

① 5킬로그램 봉지에 넣어본 후, 남은 설탕들을 3킬로그램 봉지에 넣어본다.

② 3킬로그램 봉지에 모두 다 들어가지 않으면, 5킬로그램 봉지를 하나씩 풀어 다시 3킬로그램 봉지에 넣어본다.

이것을 식으로 적으면 아래의 소스코드와 같다.

소스코드

/*
 * 백준 2839번: 설탕 배달
 */

#include <iostream>

using namespace std;

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

	if (N % 5 == 0) {
		cout << N / 5;
	}
	else {
		int num = N % 5;
		int bag3 = -1;
		int bag5 = 0;
		for (int i = N / 5; i >= 0; i--) {
			if (num % 3 == 0) {
				bag3 = num / 3;
				bag5 = i;
				break;
			}

			num += 5;
		}

		cout << bag3 + bag5;
	}

	return 0;
}