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

---

 

백준 - 단계별로 풀어보기 [2839] 

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

 

문제

 

 

설탕의 무게 N을 입력받고, 3kg짜리 봉지와 5kg 짜리 봉지를 섞어서 가져가는 경우의 수 중, 가장 최소 개수의 봉지를 구하는 문제이다.

 

풀이

 

결국 최소의 봉지를 들고가려면, 5kg짜리 봉지를 최대한 많이 활용하여야 하기 때문에, 설탕의 무게 N을 먼저 5로 나눠 본 후에, 3으로 나눠 떨어진다면 바로 정답 출력, 아니라면 5kg 봉지를 한 개씩 줄여나가면서 최소 개수의 봉지를 구하면 된다.

 

 

 

코드

 

#include <iostream>
using namespace std;
int main() {
    int kg;
    cin >> kg;
    int a,b;
    a = kg/5;
    while(1)
    {
        if(a < 0)
        {
            cout << "-1";
            return 0;
        }
        if((kg-(5*a))%3 == 0)
        {
            b = (kg-(5*a))/3;
            break;
        }
        a--;
    }
    cout << a+b;
    return 0;
}

 

 

평가

 

대표적인 Greedy Algorithm류 문제이다. 5kg으로 먼저 나눠가면서 3kg 봉지의 수를 늘려나가는 식의 방식을 고안만 할 수 있다면 쉽게 풀 수 있는 문제였을 것이지만, 그리디 알고리즘을 처음 접해보는 사람들에게는 다소 막막할 수 있는 문제이다. 정답률은 30%로 생각보다 아주 낮은 정답률을 가지고 있다.