[Baekjoon] C++ 2839번 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

 

이 문제는 두 가지 방법으로 해결 할 수 있다.

 

방법 1

규칙을 구해서 구현할 수 있다.

 

[규칙]

먼저 N이 10 이상일 경우,

끝자리가 0 또는 5라면 3kg는 1개

끝자리가 3 또는 8이라면 3kg는 2개

끝자리가 1 또는 6이라면 3kg는 3개

끝자리가 2 또는 7이라면 3kg는 4개

 

가 필요하다는 규칙을 발견할 수 있다.

​

따라서 3kg가 몇개가 필요한 지 먼저 구해주면,

나머지 값은 5의 배수가 되므로

​

 (N -3*(3kg 설탕 봉지 개수)) /5 

​

의 값이 5kg짜리 설탕 봉지의 개수이다.

if (10 <= N && N <= 5000) {
		if (N % 10 == 0) {
			three = 0;
		}
		else if (N % 10 == 3 || N % 10 == 8) {
			three = 1;
		}
		else if (N % 10 == 1 || N % 10 == 6) {
			three = 2;
		}
		else if (N % 10 == 4 || N % 10 == 9) {
			three = 3;
		}
		else if (N % 10 == 2|| N % 10 == 7) {
			three = 4;
		}
		five = (N - 3 * three) / 5;
		cout << five + three << "\n";
	}

 

 

 

N이 10 이하일 경우도 구해야한다.

이 때에는 3과 5로 N을 만들 수 있는 경우는 딱 세 가지 뿐이다.

1. N == 3 (3kg 1개)

2. N == 5 (5kg 1개)

3. N == 8 (3kg, 5kg 각각 1개)

 

이 외의 경우는 N을 만들 수 없으므로 -1을 출력한다.

if (3 <= N && N < 10) {
	if (N % 3 == 0) {
		cout << N / 3 << "\n";
	}
	else if (N % 5 == 0) {
		cout << N / 5 << "\n";
	}
    else if (N == 8) {
        three = 1;
        five = 1;
        cout << three + five << "\n";
    }
	else {
		cout << -1 << "\n";
	}
}

 

 

---

 

방법 2

 

가장 적은 개수의 봉지를 찾는 것은, 5kg을 가장 많이 가져가는 것이다.

하지만 단순히 n / 5를 하게 되면 나머지가 딱 3의 배수로 나누어 떨어지지 않는다는 문제가 발생한다.

따라서 3kg를 가장 적게 가져가서 나머지를 5kg으로 채우면 문제를 쉽게 해결할 수 있다. 

 

이를 위해서는, 나머지가 5의 배수가 되기 전까지 3kg을 추가하면 된다.

 

아래의 예시와 같이 N = 14kg인 경우 5kg를 먼저 최대로 채우면 1kg의 나머지가 발생한다.

하지만 두 번째 그림처럼 나머지가 5의 배수가 될 때까지 3kg를 먼저 채우면 3kg 3개, 5kg 1개를 채워 14kg을 만들 수 있다.

 

 

 

while문을 통해 N % 5의 나머지가 0이 될 때 까지 3kg 봉지를 추가해준다.

이때, N이 3보다 작아지면 어떻게해서도 N을 만들 수 없으므로

boolean b을 통해 N을 만들 수 없음을 기록하고 while문을 빠져나온다.

 

마지막으로 b를 확인하여 N을 만들 수 있으면 총 봉지의 개수를,

만들 수 없다면 -1을 출력한다.

이렇게 하면 방법 1보다 코드의 가독성이 훨씬 좋아진다.

bool b = 0;

while (N % 5 != 0) {
	if (N < 3) {
		b = 1;
		break;
	}
	three++;
	N -= 3;
}
	
if (b == 0) {
	five = N / 5;
	cout << five + three << "\n";
}
else cout << -1 << endl;

 

 

 

---

[전체 코드 1]

#include <iostream>
using namespace std;

int N = 0;
int three, five = 0;

int main() {

	cin >> N;

	if (10 <= N && N <= 5000) {
		if (N % 10 == 0) {
			three = 0;
		}
		else if (N % 10 == 3 || N % 10 == 8) {
			three = 1;
		}
		else if (N % 10 == 1 || N % 10 == 6) {
			three = 2;
		}
		else if (N % 10 == 4 || N % 10 == 9) {
			three = 3;
		}
		else if (N % 10 == 2|| N % 10 == 7) {
			three = 4;
		}
		five = (N - 3 * three) / 5;
		cout << five + three << "\n";
	}

	if (3 <= N && N < 10) {
		if (N % 3 == 0) {
			cout << N / 3 << "\n";
		}
		else if (N % 5 == 0) {
			cout << N / 5 << "\n";
		}
        else if (N == 8) {
			three = 1;
			five = 1;
			cout << three + five << "\n";
		}
		else {
			cout << -1 << "\n";
		}
	}
}

 

 

[전체 코드 2]

#include <iostream>
using namespace std;

int main() {


	int N = 0;
	cin >> N;
	
	int three = 0, five = 0;

	bool b = 0;

	while (N % 5 != 0) {
		if (N < 3) {
			b = 1;
			break;
		}
		three++;
		N -= 3;
	}
	
	if (b == 0) {
		five = N / 5;
		cout << five + three << "\n";
	}
	else cout << -1 << endl;
	
}