[백준(BOJ)] 2839번 설탕배달 C++ (그리디 알고리즘)

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

2839번: 설탕 배달

 

금액의 최소 화폐 개수를 세는 문제인 5585번과는 약간 다르다. 

5585번은 일단 모든 화폐가 서로 배수이고 약수인 관계이기 때문에 무작정 나눠도 되지만,

이 문제 같은 경우는 설탕을 서로 배수나 약수가 아닌 5kg, 3kg으로 정확히 나눠야 한다. 

 

그리디 알고리즘을 통해 설탕을 가장 적은 개수의 봉지로 배달하려면 3kg보다 5kg으로 나누어 떨어지는 것이 좋다.

따라서, 입력받은 설탕의 무게가 0 이상일 때,  5로 나누어 떨어질 때까지 3씩 빼며(cnt 1 증가) while문을 순회한다.

만약 무게가 5로 나누어 떨어진다면 무게를 5로 나눈 값 만큼 cnt를 증가시킨 후 cnt를 출력하고 main함수를 종료한다.

예외처리 : 만약 main함수가 종료되지않고 while문이 끝났다는 것은 입력받은 설탕의 무게가 5kg, 3kg으로 정확히 나누어 배달할 수 없음을 의미하므로 문제의 조건에 맞게 -1 출력

 

#include <iostream>
using namespace std;

int main(){
    int a;
    cin >> a;
    int cnt =0;
    while (a>=0){
        if(a%5==0){
            cnt += a/5;
            cout << cnt;
            return 0;
        }

        a-=3;
        cnt++;

    }
    cout << -1 ;
}

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/2839.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.