[BOJ][Java] 2343번 기타 레슨

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/2343

 

연속된 배열에서 M개의 블루레이에 모든 기타 강의 동영상을 녹화할 때 블루레이의 최소 크기를 구하는 문제다.

N이 100,000 이기 때문에 완탐은 불가능하고

강의의 순서는 변경되지 않는다는것에서 이진탐색을 사용하면 풀 수 있다는 힌트를 얻어야 한다.

 

이진탐색의 시작과 끝 인덱스를 찾아야 하는데

여기서 시작인덱스는 주어진 강의중 가장 시간이 긴 강의의 시간(만약 블루레이의 개수 M 이 N이라고 한다면 블루레이 하나당 최소한의 크기는 N개의 강의중 가장 시간이 긴 강의가 되기 때문) 

끝 인덱스는 만약 M이 1이라고 한다면 모든 강의를 전부 포함해야 하기 때문에 모든 강의시간들의 합이 끝 인덱스가 된다.

 

따라서 시작 인덱스(가장 시간이 긴 강의) 부터 끝 인덱스 (모든 강의시간들의 합)을 기준으로 이진탐색을 실행하며

블루레이의 개수가 M 이하이면서 블루레이의 크기가 가장 작은 경우를 구하면 된다.

 

주의해야할 점은 주어진 블루레이의 개수가 M개라고 해서 무조건 M개의 블루레이를 모두 사용할 필요는 없다는 것이다.

 

package boj;

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        int max = 0;
        int sum = 0;

        for(int i = 0; i < arr.length; i++){
            int temp = Integer.parseInt(st.nextToken());
            if(max < temp) max = temp;
            sum += temp;
            arr[i] = temp;
        }

        int start = max;
        int end = sum;
        int idxNum = 0;

        while(start <= end){
            int mid = (start + end) / 2;
            int tempSum = 0;
            int count = 0;

            for(int i = 0; i < arr.length; i++){
                if(tempSum + arr[i] <= mid){
                    tempSum += arr[i];
                }else{
                    count++;
                    tempSum = arr[i];
                }
                if(i == arr.length - 1){
                    count++;
                }
            }

            if(count <= M){
                idxNum = mid;
                end = mid - 1;
            }
            else start = mid + 1;
        }

        System.out.println(idxNum);
    }
}