[JAVA] 백준 2839번 설탕 배달 - 모든 풀이법 (그리디, DP, BFS, 완전탐색, 시간 복잡도 O(1))

백준 2839번 설탕 배달

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

 

정답 비율 38.16%라 어려울 줄 알았는데 생각보다 너무 간단하게 통과했다.

다른 풀이 방법을 찾아봤는데, 다양한 풀이 방법이 있어 공부 및 기록할 겸 글을 작성했다.

---

개요

입력받은 설탕 무게 N을 정확하게 배달해야한다.

3kg 봉지와 5kg 봉지가 있는데, 최대한 적은 봉지를 활용하여 배달해야한다.

정확하게 N kg을 만들 수 없다면 -1을 출력한다.

접근

import java.io.*;
public class Main {
    public static void main(String [] args) throws IOException{
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

     int sugar = Integer.parseInt(br.readLine());

     for(int kg3 = 0; kg3 <= sugar/3; kg3++){
         for(int kg5 = 0; kg5 <= sugar/5; kg5++){
             if(5*kg5 + 3*kg3 == sugar) {
                 bw.write(kg5 + kg3 + "\n");
                 bw.flush();
                 return;
             }
         }
     }
     bw.write(-1 + "\n");
     bw.flush();
    }
}

 

코드 설명

2중 for문으로 접근하였다. 3kg 봉지를 적게 사용해야 하기 때문에, 첫번째 for문에 위치시켰다.

sugar : 배달해야 하는 설탕의 무게 N
kg3 : 3kg 봉지의 개수
kg5 : 5kg 봉지의 개수

3kg봉지가 0개일때, 5kg봉지 개수를 늘려가며 조건을 만족하는지 찾는다. 만족하지 않으면, 3kg봉지 하나일때의 조건으로 넘어감.
3kg봉지가 1개일때, 위와 동일하게 탐색.

 

내가 푼 방법은 완전 탐색(Brute Force) 방식으로, 시간 복잡도가 O(N²)이다. 비효율적인 방법이지만 직관적이고 쉽다. 하지만 입력 데이터가 증가하면 시간초과가 될 수 있기 때문에 다른 방식으로 접근하는 것이 좋다.

---

다른 방법

방법	시간 복잡도
그리디	O(N)
DP(동적 계획법)	O(N)
BFS(너비 우선 탐색)	O(N)
수학적 접근	O(1)

---

1. 그리디 알고리즘

import java.io.*;
public class Solve2839Greedy {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int sugar = Integer.parseInt(br.readLine());
        //사용하는 봉지의 개수를 저장할 변수 count
        int count = 0;
        
        while(sugar >=0){
        //설탕의 무게가 5로 나눠떨어지면? (5의 배수라면)
            if(sugar % 5 == 0){
                count += sugar/5;
                bw.write(count + "\n");
                bw.flush();
                return;
            }
        //설탕의 무게가 5의 배수가 아니라면 3을빼고, 3kg봉지 하나를 쓴 것으로 간주
            sugar -= 3;
            count++;
        }
        //설탕의 무게가 0보다 작거나 같아졌다면? -1출력 (조건 만족못함)
        bw.write(-1 + "\n");
        bw.flush();
    }
}

 

너무 간단하게 구현 가능하다. 반복문 하나로 해결 가능함. 

설탕의 무게를 3씩 줄여가면서 5의 배수인지 탐색하는 조건이다.

---

2. DP(동적 계획법)

import java.io.*;
public class Solve2839DP {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int sugar = Integer.parseInt(br.readLine());
        int [] dp = new int[sugar + 1];

        //dp[i]에서 i는 설탕의 무게, dp[i]의 값은 봉지의 개수를 의미함.
        for(int i = 0; i <= sugar; i++){
            dp[i] = 5001; //가장 큰 값(범위를 벗어나는 값을 저장해 초기화)
        }
        dp[0] = 0;
        //1, 2kg는 고려할 필요가 없기 때문에 i=3부터 시작함.
        //dp[3] = Math.min(dp[3], dp[0] + 1); 에서, dp[3]은 5001로 초기화 되어 있기 때문에
        //dp[3] = dp[0] + 1 = 1이 됨.
        for(int i = 3; i <= sugar; i++){
            if(i >= 3) dp[i] = Math.min(dp[i], dp[i-3] + 1);
            if(i >= 5) dp[i] = Math.min(dp[i], dp[i-5] + 1);
        }
        //만약 해당 설탕의 무게를 계산할 수 없다면 -1 출력. 아니면 봉지 개수 출력.
        bw.write((dp[sugar] >= 5001? -1 : dp[sugar]) + "\n");
        bw.flush();
    }
}

 

위 코드에서 이해를 돕기 위해 추가 설명을 해보겠다.

i = 5일때, 

if(i >= 3) 에서, dp[5] = Math.min(dp[5], dp[2] + 1); 이기 때문에 값 변경없이 dp[5] = 5001로 다음 조건으로 넘어간다.

if(i >= 5) 에서, dp[5] = Math.min(dp[5], dp[0] + 1); 

dp[5] = dp[0] + 1 = 1이 된다.

 

i = 6 일때,

if(i >= 3) 에서, dp[6] = Math.min(dp[6], dp[3] + 1); 

dp[6] = dp[3] + 1 = 2가 된다.

if(i >= 5) 에서, dp[6] = Math.min(dp[6], dp[1] + 1); 에서 dp[1] + 1 = 5002기 때문에, dp[6] = 2으로 값 변경 없이 넘어간다.

---

3. BFS(너비 우선 탐색)

BFS 알고리즘을 사용하는 이유?

Nkg를 만드는 최소 갯수를 구하기 때문에, 최단 경로 탐색과 비슷하게 접근할 수 있다.

import java.io.*;
import java.util.*;
public class Main {
	//BFS 알고리즘 구현
    public static int bfs(int sugar) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> visited = new HashMap<>(); //{무게, 봉지 개수}
        queue.add(sugar);
        visited.put(sugar, 0); //시작점 (Nkg, 0봉지)

        while (!queue.isEmpty()) {
            int current = queue.poll(); //현재 남은 설탕 무게 반환.
            int count = visited.get(current); //현재까지 사용된 봉지 개수.

            //정확히 나누어 떨어졌다면 봉지 개수 반환.
            if (current == 0) return count;

            //5kg 봉지 사용하고,
            if (current >= 5 && !visited.containsKey(current - 5)) {
                queue.add(current - 5); //5를 뺀 설탕 무게 최신화
                visited.put(current - 5, count + 1);
            }
            //3kg 봉지 사용
            if (current >= 3 && !visited.containsKey(current - 3)) {
                queue.add(current - 3);
                visited.put(current - 3, count + 1);
            }
        }
        return -1;
    }
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int sugar = Integer.parseInt(br.readLine());

        bw.write(bfs(sugar) + "\n");
        bw.flush();
    }
}

 

코드 흐름

(sugar = 10일 때)

Step 1: 초기 상태

queue = [10]
visited = {10 : 0}
current = 10, count = 0

 

Step 2: 10에서 5kg, 3kg 빼기

queue = [5, 7] // 10-5, 10-3
visited = {10:0, 5:1, 7:1}
current = 5, count = 1

 

Step 3: 5에서 5kg, 3kg 빼기.

queue = [7, 0, 2] // 5-5, 5-3
visited = {10:0, 5:1, 7:1, 0:2, 2:2}
current = 0, count = 2
//0이 나왔기 때문에, 더 탐색할 필요 없음. 프로그램 종료.

 

 

완전탐색은 O(N²) 이고, BFS는 O(N)인데, 실제 연산 시간은 완전탐색이 조금 더 빨랐다.

왜 이런 결과가 나왔을까?

완전탐색과 BFS 시간 비교

완전탐색 코드 (이중 반복문)

• O(N^2) 이지만, 탐색 범위가 작아서 실제 연산 횟수는 많지 않다.
• 단순히 3kg, 5kg의 모든 조합을 살펴보는 구조
• N ≤ 5000이므로, 최대 연산 횟수가 약 1,670,000번 → 충분히 빠름

BFS 코드

• 이론적으로 O(N) (각 숫자를 한 번씩 방문)
• 하지만 Queue(큐) 연산, HashMap(해시맵) 조회 등이 추가로 포함됨
• 특정 값(Nkg)에 도달하는 경로가 많으면 탐색해야 할 경우의 수가 늘어남
• 특히 5kg, 3kg을 빼는 과정에서 중복되는 값들이 큐에 계속 들어갈 수도 있음
• visited 체크가 있어도, 경로마다 다르게 도달할 수 있어 탐색이 길어질 수 있음

결론적으로, 탐색 범위가 작기도 했고, BFS 알고리즘에 큐 연산, 해시맵 조회를 해야해서 시간이 더 오래걸린 것이다. 만약 탐색 범위가 더 컸다면 유의미한 차이가 났을 것이다.

---

4. 수학적 접근

그리디 알고리즘에서 반복문 없이 수식으로 해결하는 방법이다.

최선의 경우 시간 복잡도가 O(1)이다. 

import java.io.*;
public class Main {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int sugar = Integer.parseInt(br.readLine());
        
        int kg5 = sugar / 5; //5kg 주머니를 쓸 수 있는 만큼 모두 사용하기 위한 식
        while(kg5 >= 0){
            //5kg 주머니를 사용하고, 남은 무게를 저장함
            int temp = sugar - (5 * kg5);
            if(temp % 3 == 0){ //남은 무게가 3의 배수이면? 3kg주머니 모두 사용하고 출력.
                bw.write((kg5 + temp/3) + "\n");
                bw.flush();
                return;
            }
            kg5--; //기존에 사용한 5kg 주머니 개수를 줄이고 다시 탐색.
        }
        bw.write(-1 + "\n");
        bw.flush();
    }
}