BOJ_2343 : 기타 레슨

👉 문제링크

2343번: 기타 레슨

---

---

🔸 문제 분석 🔸

• N개의 영상을 M개의 블루레이에 나눠 저장하려고 한다.
• 하나의 블루레이 크기의 최소값을 구한다.

🔸 문제 풀이 🔸

• 블루레이 크기를 이진 탐색으로 찾는다.
  • 최소 크기는 N개의 영상 중 최대값
  • 최대 크기는 N개의 영상의 총합
  • 중앙값을 시작으로 M개의 블루레이에 모두 저장할 수 있으면 크기를 줄여보고,
    모두 저장할 수 없으면 저장 크기를 늘려보는 식으로 탐색한다.

🔸 코드 🔸

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());

        int start = 0; // 시작 인덱스 :
        int end = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            start = Math.max(start, arr[i]);
            end += arr[i];
        }

        while (start <= end) {
            int mid = (start + end) / 2;
            int sum = 0;
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                if (sum + arr[i] > mid) {
                    sum = 0;
                    cnt++;
                }
                sum += arr[i];
            }
            if (sum > 0) cnt++;
            if (cnt > M) start = mid + 1;
            else end = mid - 1;
        }

        bw.write(Integer.toString(start));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 이진탐색으로 블루레이 크기의 최소값을 구한다.
  • 시작 인덱스는 영상 중 최대값(블루레이가 이 보다 작으면 저장할 수 없다)
  • 마지막 인덱스는 영상의 총합(블루레이가 더 커질 필요가 없다)
• 중앙값 mid는 현재 블루레이의 크기이다.
• sum은 현재 블루레이에 저장한 영상 길이의 합, cnt는 현재까지 사용한 블루레이의 개수이다.
  • 저장한 영상이 mid보다 길어지면 cnt를 + 1한다.
• 모든 영상을 확인한 후 다음 탐색을 진행한다.
  • cnt > M 이면, 블루레이 공간이 부족했다는 것이므로 start를 mid+1로 바꾼다.
  • cnt <= M 이면, 블루레이 공간이 적합하거나 넘쳤다는 것이므로 end를 mid-1로 바꾼다.

---

🔸 end 🔸

• 이진 탐색을 단순 배열 탐색에 이용하는 것이 아니라 값에 적용한 문제이다.
  • 이렇게 쓰인다는 것은 알고 있었지만, 아직 익숙해지지 않았다.
  • 이런 방식의 문제를 더 풀어봐야 할 것 같다.
  • 이런 방식의 이진 탐색을 매개 변수 탐색이라고 부르는 것 같다.