(매일 BOJ) C++ 2839번 설탕 배달

이번 문제는 실버 4 난이도의 2839번 설탕 배달 문제이다.

문제 요약

N kg의 설탕을 3kg 또는 5kg 봉지에 담아서 최소 개수로 배달해야 한다.
정확히 Nkg을 만들 수 없으면 -1을 출력한다.

 

접근법 : Greedy

 5kg 봉지를 최대한 많이 쓰고, 남는 걸 3kg로 채워보자.

• N을 5로 나눈 몫만큼 5kg을 써보고
• 남는 무게가 3으로 나눠떨어지는지 확인
• 안 되면 5kg을 하나 줄이고 다시 시도

 

아래는 작성한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);

    int n, count = 0;
    cin >> n;
    while (n >= 0){ // N이 음수면 -1 출력
        if (n % 5 == 0){  // 그리디 사용
            count += n / 5; // 5부터 채우기
            cout << count;
            return 0;
        }
        n -= 3; // 조건 충족 x > -3 한 후 다시 5 채우기
        count += 1;
    }

    cout << -1;
}