[Java] 백준 2343번 기타 레슨

이분 탐색 문제입니다.

N개의 강의를 M개 이하의 블루레이로 녹화할 때 최소 길이를 구해야합니다.

길이를 기준으로 이분탐색을 진행해서 가능한 경우를 찾고
가능하다면 더 짧은 길이가 있는지, 불가능 하다면 더 긴 길이를 탐색하게 하였습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int result = 1_000_000_000;
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[] arr = new int[n + 1];
    int[] prefixSum = new int[n + 1];

    st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
      prefixSum[i] = arr[i] + prefixSum[i - 1];
    }

    int left = 0;
    int right = 1_000_000_000;
    while (left <= right) {
      int mid = (left + right) / 2;
      int start = 0;
      int sum = 0;
      int cnt = 0;
      for (int i = 1; i <= n; ++i) {
        if (prefixSum[i] - prefixSum[start] > mid) {
          sum = Math.max(sum, prefixSum[i - 1] - prefixSum[start]);
          start = i - 1;
          ++cnt;
        }
      }
      sum = Math.max(sum, prefixSum[n] - prefixSum[start]);
      ++cnt;

      if (cnt > m) {
        left = mid + 1;
      } else if (cnt <= m) {
        result = Math.min(result, sum);
        right = mid - 1;
      }
    }

    bw.write(result + "\n");
    bw.close();

  }
}