📘 백준 문제 풀이: 블루레이 만들기

백준 문제 "블루레이 만들기"를 풀어보겠습니다. 이 문제는 이분 탐색(Binary Search) 기법을 활용하여 최적의 블루레이 크기를 구하는 문제입니다. 아래는 문제 접근 방법과 구현 코드입니다.

문제 설명

📝 문제 조건

강의가 총 n개 주어집니다.
강의를 담을 블루레이 m개가 있습니다.
각 블루레이는 모든 강의를 포함해야 하며, 강의 순서를 바꿀 수 없습니다.
블루레이 크기를 최소화해야 합니다.

🔑 문제 풀이 아이디어

블루레이의 최소 크기는 가장 긴 강의 시간입니다.
블루레이의 최대 크기는 모든 강의 시간의 합입니다.
이분 탐색을 사용하여 가능한 블루레이 크기 중 최소값을 찾아냅니다.
- 특정 크기 mid로 블루레이를 나눴을 때 m개 이하로 나눌 수 있다면, 더 작은 크기로 시도합니다.
- m개를 초과하면 블루레이 크기를 늘려야 합니다.

코드 구현

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());

        int[] arr = new int[n];
        int maxLecture = 0, totalSum = 0;

        // 강의 시간을 입력받음
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            totalSum += arr[i];
            maxLecture = Math.max(maxLecture, arr[i]);
        }

        // 이분 탐색: 블루레이 크기 탐색
        int left = maxLecture, right = totalSum;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (isPossible(arr, n, m, mid)) {
                right = mid - 1; // 더 작은 크기를 시도
            } else {
                left = mid + 1; // 더 큰 크기를 시도
            }
        }

        System.out.println(left);
    }

    // 블루레이 크기 `size`로 가능한지 확인
    private static boolean isPossible(int[] arr, int n, int m, int size) {
        int count = 1, currentSum = 0;
        for (int time : arr) {
            if (currentSum + time > size) {
                count++;
                currentSum = 0;
            }
            currentSum += time;
        }
        return count <= m;
    }
}

코드 설명

1️⃣ 입력 처리

강의 수 n과 블루레이 수 m을 입력받습니다.
각 강의 시간을 배열 arr에 저장하며, 가장 긴 강의 시간과 전체 합을 계산합니다.

2️⃣ 이분 탐색

블루레이 최소 크기는 maxLecture (가장 긴 강의 시간)입니다.
블루레이 최대 크기는 totalSum (모든 강의 시간의 합)입니다.
left, right를 설정하고, 이분 탐색으로 가능한 블루레이 크기를 탐색합니다.

3️⃣ 가능한 블루레이 크기 확인

특정 크기 mid로 강의를 나누었을 때 필요한 블루레이 개수를 계산합니다.
블루레이 개수가 m개 이하라면 크기를 줄이고, 초과하면 크기를 늘립니다.

시간 복잡도

이분 탐색: 최대 O(log(totalSum - maxLecture))
블루레이 크기 확인: 배열 순회 O(n)
전체 시간 복잡도: O(n log(totalSum - maxLecture))