[백준/c++] BOJ 2839 - 설탕 배달

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

2839번: 설탕 배달

 

문제 설명

상근이는 정확하게 N 킬로그램의 설탕을 배달해야 한다. 설탕은 3킬로그램, 5킬로그램 봉지에 담겨 있으며 정확히 N킬로그램을 배달해야 한다. 최대한 적은 봉지를 가져갈 때, 봉지의 개수를 구해야 한다.

(3 <= N <= 5000)

 

해결

최대한 적은 봉지를 가져가야 하므로, N 킬로그램을 5킬로그램 봉지로 채울 수 있는 만큼 많이 채워야 한다.

전체적인 로직은 다음과 같다.

 

1. N이 5의 배수라면 바로 5로 나눈 몫을 출력한다.

2. N이 5보다 클 동안 5를 빼 주고, five 변수값 (5가 몇 번 나눠졌는지 저장)을 증가시켜 준다.

3. N에서 3을 빼고, three 변수값 (3이 몇 번 나눠졌는지 저장)을 증가 시킨다.

4. N이 0보다 작고, five 값이 0보다 클 동안, N에 다시 5를 더한 후, 3을 빼 준다. (five--, three++)

5.  N이 3보다 크거나 같을 동안 3을 빼고, three 변수값을 증가시킨다.

6. N이 0보다 클 동안 3~5를 반복한다.

7. 반복문을 탈출한 N이 0이 아니라면 -1, 0이라면 three + five 값을 출력한다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int arr[5005];

int main() {
	int n, five = 0, three = 0;
	cin >> n;
	if (!(n % 5)) {
		cout << n / 5;
		return 0;
	}

	while (n - 5 >= 0) {
		n -= 5;
		five++;
	}
	while (1) {
		n -= 3; three++;
		for (int i = five; i > 0; i--) {
			if (n >= 0) break;
			n += 2;
			five--; three++;
		}
		while (n - 3 >= 0) {
			n -= 3; three++;
		}

		if (n <= 0) break;

	}



	if (n) {
		cout << "-1";
		return 0;
	}
	cout << five + three;
}