[백준][BOJ 2343] - 기타 레슨

문제

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

2343번: 기타 레슨

 

 

문제 접근

• 나이브한 접근법으로는 블루레이의 크기를 1씩 올려가며 몇 개의 블루레이 디스크가 나올 수 있는지를 확인하는 것이다.
  • 1씩 증가시켜 확인할 때 M개의 블루레이 디스크로 나뉘어질 수 있다면 해당 크기를 반환하고 종료하는 코드를 구현하면 될 것이다.
  • 하지만 해당 방식을 사용하면 매우 비효율적일 수 있다. 당장 강의의 수가 10만까지 올라갈 수 있고, 각 강의의 길이가 1만분까지로 되어 있을 때 따져볼 수 있는 경우의 수는 100억 가까이 된다.
  • 심지어 100억에 가까운 경우의 수에 대해 10만개의 강의의 수를 탐색하며 M개의 블루레이 디스크로 나뉘어질 수 있는지도 확인해야 하므로 시간 초과가 걸릴 수 있다.
• 블루레이 디스크의 크기 $K$를 이분 탐색으로 접근하여 구현할 수 있다.
  • 이때 초기에 사용할 범위를 잘 잡아야 하는데 시작 범위는 강의들 중 가장 긴 시간으로 잡아야 한다. 그래야지 모든 강의들이 블루레이 디스크에 들어갈 수 있기 때문이다.
  • 끝 범위는 하나의 블루레이 디스크에 모든 강의가 들어가는 경우로 이는 모든 강의 시간의 총합이다.
  • 이를 사용하여 이분 탐색을 구현할 수 있다.
    • 만약 중간값으로 나온 블루레이 크기를 사용하였을 때 산출되는 블루레이 디스크 필요 양이 $M$보다 크다면, 블루레이 크기는 더 커져야 한다. 그래야지 더 많은 강의들을 넣을 수 있기 때문이다.
    • 만약 $M$보다 작거나 같다면 그대로 사용하면 된다.
  • 이때 $M$보다 작은것도 왜 답이 되는가 라는 생각이 들 수 있다. 이는 문제에서 보면 블루레이 디스크의 크기가 모두 동일해야 한다는 제약조건만 있으며 반드시 용량을 최대한 채워야 한다는 제약조건이 없다.
  • 즉 하나의 블루레이 디스크에 다 차지 않아도, 새로운 블루레이 디스크를 사용하여 강의를 넣을 수 있다는 것이다. 따라서 $M$보다 작다면 어떻게든 블루레이 디스크의 필요량을 $M$개로 뻥튀기 시킬 수 있다.

 

 

정답 코드

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());

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

    int[] lectureLength = new int[N];

    long sum = 0L;
    int maxLectureLength = Integer.MIN_VALUE;
    st = new StringTokenizer(br.readLine());

    for (int i = 0; i < N; i++){
      lectureLength[i] = Integer.parseInt(st.nextToken());
      maxLectureLength = Math.max(maxLectureLength, lectureLength[i]);
      sum += lectureLength[i];
    }

    if (N == M){
      System.out.println(maxLectureLength);
      return;
    }

    if (M == 1){
      System.out.println(sum);
      return;
    }

    long start = maxLectureLength;
    long end = sum;
    long ans = Long.MAX_VALUE;

    while(start < end){
      long mid = (start + end) / 2;

      long partSum = 0L;
      int cnt = 1;

      for (int i = 0; i < N; i++){
        if (partSum + lectureLength[i] > mid){
          partSum = 0L;
          cnt++;
        }

        partSum += lectureLength[i];
      }

      if (cnt > M){
        start = mid + 1;
      } else {
        ans = Math.min(ans, mid);
        end = mid;
      }
    }

    System.out.println(ans);
  }
}