[JAVA][Baekjoon] 2343번 기타 레슨 🌟

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

📌 접근 방식

이 문제는 주어진 강의들을 최소한의 블루레이 크기로 M개의 블루레이에 나누어 담는 문제이다.

중요한 점은 블루레이에 담는 강의의 순서가 바뀌면 안 된다는 것!!

이 문제를 해결하기 위해서는 이진 탐색을 사용하여 최소 가능한 블루레이 크기를 찾을 수 있었다.

 

1️⃣ 블루레이의 최소 크기

블루레이에 강의들을 담을 때, 최소 크기는 가장 긴 강의가 될 수밖에 없다
➡️ 블루레이에는 강의가 순서대로 들어가야 하기 때문에, 그 강의보다 작은 크기의 블루레이는 하나의 강의도 담을 수 없기 때문

 

2️⃣ 블루레이의 최대 크기

최대 크기는 모든 강의를 하나의 블루레이에 담았을 때의 크기 즉, 모든 강의의 총 합

 

3️⃣ 이진 탐색을 활용

이진 탐색을 통해 가능한 블루레이의 크기 범위를 좁혀가며 최소 크기를 찾는다. 중간값(mid)을 계산하여, 그 크기로 강의들을 M개의 블루레이에 나누어 담을 수 있는지 확인한다.

• 강의들을 하나씩 블루레이에 담다가, 현재 블루레이에 담을 수 없으면 새로운 블루레이를 시작
• M개의 블루레이를 넘기지 않도록 체크하고, 넘기면 블루레이 크기를 늘려보고, 넘지 않으면 더 작은 크기로 시도

[알고리즘] 이진 탐색(Binary Search)

 

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 강의 수 N, 블루레이 개수 M
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        // 강의 길이 배열 A
        st = new StringTokenizer(br.readLine());
        int[] A = new int[N];
        int start = 0; // 블루레이의 최소 크기 (가장 긴 강의 길이)
        int end = 0; // 블루레이의 최대 크기 (모든 강의 길이의 합)
        
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            if(start < A[i]) {
                start = A[i]; // 가장 긴 강의 길이를 최소 크기로 설정
            }
            end += A[i]; // 모든 강의 길이의 합을 최대 크기로 설정
        }
        
        while (start <= end) {
            int middle = (start + end) / 2; // 중간값 계산
            int sum = 0; // 현재 블루레이에 담긴 강의 길이 합
            int count = 1; // 블루레이의 개수, 최소 1개는 필요

            for (int i = 0; i < N; i++) {
                if (sum + A[i] > middle) { // 현재 블루레이에 담을 수 없으면
                    count++; // 새로운 블루레이 시작
                    sum = 0; // 블루레이 초기화
                }
                sum += A[i]; // 강의를 현재 블루레이에 담기
            }

            if (count > M) { // M개보다 많은 블루레이가 필요하면
                start = middle + 1; // 크기를 키워야 한다
            } else {
                end = middle - 1; // 크기를 줄여본다
            }
        }
        System.out.println(start); // 가능한 최소 블루레이 크기 출력
    }
}

✅ 이진 탐색을 위한 범위 설정:

• start는 최소 블루레이 크기로, 가장 긴 강의의 길이로 설정
• end는 최대 블루레이 크기로, 모든 강의의 총 길이로 설정

 

✅ 이진 탐색:

• start부터 end까지 범위에서 middle 값을 계산하고, 해당 크기로 블루레이에 강의를 나누어 담을 수 있는지 확인
• 강의들을 middle 크기의 블루레이에 나누어 담을 수 있으면 end를 middle - 1로 줄이고, 그렇지 않으면 start를 middle + 1로 늘린다.

 

 

😊 느낀 점

처음에는 '블루레이'라는 개념 자체가 조금 낯설어서 문제를 풀기 전에 많이 헷갈렸다. 또한, 강의 순서가 반드시 유지되어야 한다는 점에서 강의를 나누는 과정이 어려웠다. 강의를 나누는 과정에서 각 강의가 들어갈 블루레이의 크기가 기존 크기를 넘지 않도록 하는 부분이 생각보다 까다로웠다. 강의 길이를 모두 더해서 하나의 블루레이에 넣을 수 있는지 확인하고, 그 블루레이가 넘지 않도록 적절히 분배하는 과정이 쉽지 않았다. 이진 탐색을 이용하여 구현하였는데, 중간값을 계산해가며 점차적으로 최소 크기를 찾아가면서 구할 수 있었다!

처음엔 조금 헷갈렸지만, 끝까지 고민하면서 풀게 되어 뿌듯했다! 😊