[알고리즘] 백준 > #2343. 기타 레슨

문제링크

백준 #2343. 기타 레슨

풀이방법

전에 풀었던 이진탐색문제와 아주 비슷하게 생겨서 보자마자 이진탐색을 이용하면 되겠다고 생각했다. 즉, begin, end 값을 최초에 설정해두고 툭툭 값을 던져보면서 그 범위를 반으로 나눠나가는 방식을 이용했다. N과 레슨의 최대 길이를 고려했을 때 최대 O(log1,000,000,000)의 시간복잡도를 가지기 때문에 가능한 풀이방법이라고 생각했다! 여기서 begin은 블루레이의 크기가 될 수 없는 값 중 가장 큰 값이고 end는 최소 블루레이 크기로 설정했다.

+) 한 레슨의 크기가 블루레이의 크기보다 큰 경우를 꼭 고려해야한다!

코드

import java.util.*;
public class BOJ2343 {

    static int n, m;
    static int[] numArray;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        numArray = new int[n];
        for (int i = 0; i < n; i++) numArray[i] = sc.nextInt();

        int begin = 0;
        int end = 1000000000;

        while ((end - begin) > 1) {
            int mid = (begin + end) / 2;

            if (isPossibleLength(mid)) end = mid;
            else begin = mid;
        }

        System.out.print(end);
    }

    private static boolean isPossibleLength(int length) {
        int tempSum = 0;
        int count = 1;
        for (int i = 0; i < n; i++) {
            if (numArray[i] > length) return false;

            if ((tempSum + numArray[i]) > length) {
                tempSum = numArray[i];
                if (++count > m) return false;
            } else tempSum += numArray[i];
        }

        return true;
    }
}