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

문제

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

 

문제 내용

Nkg의 설탕을 3kg 또는 5kg 봉지로 나누어 담아야 한다.
이때, 정확하게 Nkg을 만들면서 봉지의 개수를 최소화하는 것이 목표이다.

 

문제 풀이

Greedy를 사용하여 문제를 풀었다.

설탕이 15kg가 있다면 3kg 5봉지와 5kg 3봉지로 채울 수 있다. 
이 경우, 5kg 3봉지로 채우는 것이 정답이다.

즉, 5로 나눌 수 있다면 5kg을 사용하고, 그렇지 않다면 3kg을 사용하면 된다.

 

코드

#include <iostream>

using namespace std;
int n, cnt;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	cin >> n; //무게
	cnt = 0;

	while (n >= 0) {
		if (n % 5 == 0) {
			cnt += (n / 5);
			cout << cnt << '\n';
			return 0;
		}
		else {
			cnt ++;
			n -= 3; //3kg짜리 가방 하나를 뺀다.
		}
	}
    
    //정확하게 Nkg를 만들 수 없는 경우 -1 출력
	cout << -1 << '\n';

}

 

문제 코드 설명

1) 문제 해결

5로 나눌 수 있다면 몫을 구해서 출력하고 종료하면 된다.
그렇지 않다면 입력받은 N에서 3kg 가방 하나씩 빼면서 5로 나눌 수 있을 때까지 반복문을 돌린다.
만약 N이 음수가 될 때까지 종료되지 않는다면 반복문을 벗어나 -1을 출력하면 된다.