[BOJ 2839] 설탕 배달 - [그리디/수학]

[BOJ 2839] 설탕 배달 - [그리디/수학]

문제 링크

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

문제 요약

설탕 $N$kg을 3kg봉지와 5kg봉지를 사용하여 정확하게 배달해야 할 때, 사용하는 봉지의 최소 개수를 구하는 프로그램 작성 (정확하게 나누어 떨어지지 않으면 -1 출력).

접근 방법

• 자료구조: 정수형 변수 (int)
• 알고리즘: 그리디 알고리즘 (Greedy Algorithm)
• 핵심 아이디어: 1. 가장 큰 단위인 5kg 봉지를 최대한 많이 사용하는 것이 유리함. 2. 현재 무게 $N$이 5로 나누어떨어질 때까지 $N$에서 3kg을 하나씩 빼면서 봉지 개수를 증가시킴. 3. 만약 $N$이 0보다 작아지면 불가능한 경우로 판단.

풀이 코드

#include <iostream>

using namespace std;

int main() {
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int total_bags = 0;

    while (N >= 0) {
        // 5로 나누어 떨어지는 경우, 가장 큰 단위로 나머지를 모두 채움
        if (N % 5 == 0) {
            total_bags += (N / 5);
            cout << total_bags << "\n";
            return 0;
        }
        
        // 5로 나누어 떨어지지 않으면 3kg 봉지 하나를 사용
        N -= 3;
        total_bags++;
    }

    // N이 0 미만이 될 때까지 나누어 떨어지지 않은 경우
    cout << -1 << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N)$
  • $N$이 최대 5000이며, 최악의 경우 3씩 줄여나가므로 약 1666번 연산함. 상수 시간에 수렴하여 매우 빠름.
• 공간 복잡도: $O(1)$
  • 별도의 배열을 사용하지 않고 변수 몇 개만 사용함.

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

핵심 포인트

1. 그리디의 기준: 5로 나누어떨어지는 시점이 최적의 해라는 점을 포착하는 것이 중요합니다.
2. 반복문 종료 조건: $N$이 0보다 작아지는 순간은 정확한 배달이 불가능한 조합임을 의미합니다.
3. 효율성: DP로도 풀 수 있지만, 수학적/그리디 접근이 훨씬 직관적이고 메모리 사용량이 적습니다.

예제 확인

• 예제 1 (18): 5로 안 나눠짐 → 15(3kg1) → 5로 나눠짐(5kg3) → 결과: 4
• 예제 2 (4): 5로 안 나눠짐 → 1(3kg1) → 5로 안 나눠짐 → -2(3kg1) → 결과: -1
• 예제 5 (11): 5로 안 나눠짐 → 8(3kg1) → 5로 안 나눠짐 → 5(3kg1) → 5로 나눠짐(5kg*1) → 결과: 3