[백준 2343] 기타레슨 (이진 탐색)

 

문제의 핵심은 이진탐색이다.

 

이진탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

핵심이론은 다음과 같다.

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

문제에서는 블루레이의 크기가 모두 같고 녹화순서가 바뀌지 않아야 함 이라는 문제 조건이 이진 탐색 알고리즘을 선택하게 하는 실마리이다.

 

이진탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다. 

 

코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;



public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = new int[N];
        int start = 0;
        int end = 0;

        for (int i = 0; i< N; i++) {
            A[i] = sc.nextInt();
            if(start < A[i]) {
                start = A[i];
            }
            end += A[i];
        }

        while (start <= end) {
            int middle = (start + end) / 2;
            int sum = 0;
            int count = 0;
            for (int i = 0; i < N; i++) {
                if (sum + A[i] > middle) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            if (sum != 0)
                count++;
            if (count > M)
                start = middle + 1;
            else
                end = middle - 1;
        }
        System.out.println(start);
    }
}