백준 2839번 [설탕 배달](C++)-yes6686- 티스토리

백준 문제 풀이: 2839 [설탕 배달]

---

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

문제 설명:

설탕을 N킬로그램 배달해야 합니다. 설탕 봉지는 3킬로그램과 5킬로그램짜리 두 종류만 있습니다. 최대한 적은 봉지 개수로 N킬로그램을 배달할 수 있는 최소 봉지 개수를 구하는 문제입니다. 단, 정확히 N킬로그램을 배달할 수 없다면 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    int cnt = 0;

    while (true) {
        if (N % 5 == 0) { // 5로 나누어 떨어지면
            cnt += (N / 5);
            break;
        }
        N -= 3; // 3킬로그램 봉지를 하나 사용
        cnt++;
        if (N < 0) { // 정확히 N킬로그램 만들 수 없는 경우
            cnt = -1;
            break;
        }
    }
    cout << cnt;
}

---

코드 설명

• 핵심 알고리즘: 탐욕법을 사용하여 5킬로그램 봉지를 최대한 먼저 사용
• 구현 세부사항:
  • 5킬로그램 봉지로 나눌 수 있을 때까지 3킬로그램 봉지를 사용
  • 5로 나누어 떨어지면 해당 몫을 추가하고 종료
  • 3킬로그램 봉지를 빼다가 N이 음수가 되면 -1을 출력
• 시간 복잡도: O(N) (최악의 경우 N/3 만큼 반복)

---

결과

주어진 설탕 무게 N에 대해 최소 봉지 개수를 정확히 계산합니다. 불가능한 경우 -1을 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!