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

Junu Kim·2025년 12월 24일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

68/89

[2839] 설탕 배달

난이도: ★★☆☆☆ • solved on: 2025-12-24

문제 요약

문제 유형: 그리디 (Greedy), 완전탐색 (Brute Force)
요구사항: 정확히 Nkg을 만들기 위해 3kg, 5kg 봉지를 사용했을 때 봉지 개수의 최솟값을 출력한다. 만들 수 없으면 -1을 출력한다.

사용 개념

자료구조
- 없음
알고리즘/기법
- 방법 1: 5kg 개수(0-N/5) 브루트포스
- 방법 2: 그리디 (5kg 최대한 쓰고 3kg로 보정)
핵심 키워드
- 최소 봉지 수 (min bags)
- 나머지 (mod)
- 그리디 최적화 (greedy optimization)

풀이 아이디어 및 코드

방법 1 : 5kg 봉지 개수를 전부 시도 (브루트포스)

문제 분해

5kg 봉지 개수 y를 0부터 N/5까지 바꿔가며,

남은 무게가 3kg 봉지로 정확히 나누어 떨어지는지 확인한다.
핵심 로직 흐름
for y = 0..N/5:
    x = (N - 5y) / 3
    if 3x + 5y == N:
        answer = min(answer, x+y)
예외 처리

끝까지 못 찾으면 -1

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int minTotal = -1;
        int n = sc.nextInt();
        int x;
        int y;
        for(int i = 0; i <= n/5; i++){
            y = i;
            x = (n - 5*y)/3;
            if(3*x+5*y == n && minTotal != -1){
                minTotal = Math.min(minTotal, x+y);
            } else if(3*x+5*y==n){
                minTotal = x + y;
            }
        }
        System.out.println(minTotal);
    }
}

방법 2 : 그리디로 5kg를 최대한 쓰고, 3kg로 맞추기

브루트포스는 O(N)인데, 이 문제는 3과 5 조합 특성 때문에 최대 5번 이내의 보정으로 답을 찾을 수 있어 사실상 O(1)로 줄일 수 있다.

아이디어:

y = N/5 (5kg 최대 개수)부터 시작해서,

남은 무게가 3으로 나누어지면 종료

아니면 5kg 봉지 하나를 줄이고 다시 검사

y가 음수가 되면 불가능 → -1

개선 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int y = n / 5; // 5kg 최대 사용
        while (y >= 0) {
            int rest = n - 5 * y;
            if (rest % 3 == 0) {
                int x = rest / 3;
                System.out.println(x + y);
                return;
            }
            y--; // 5kg 하나 줄이고 재시도
        }
        System.out.println(-1);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: O(N/5) ≈ O(N)
공간 복잡도: O(1)

방법 2

시간 복잡도: O(N/5)처럼 보이지만 실제로는 y를 줄이는 횟수가 매우 제한적이라 사실상 빠르게 끝남
- (최악을 엄밀히 쓰면 while 반복이 N/5까지 갈 수 있어 O(N)이지만, 입력 범위가 작고 3·5 조합 특성상 대부분 짧게 종료)
공간 복잡도: O(1)

어려웠던 점

없음

배운 점 및 팁

같은 문제라도 “전체를 돌며 최소값”을 찾는 브루트포스 대신, 큰 단위(5kg)를 최대한 쓰고 나머지 조건(3으로 나누어떨어짐)을 만족할 때까지 보정
하는 방식이 더 간결해진다.
실전에서는 Scanner보다 BufferedReader가 보통 빠르지만 이 문제에서의 입력 횟수는 1번이기에 큰 의미는 없다.