[백준 2343번 기타 레슨 Java] 이진 탐색을 활용한 값 찾기

 

이진 탐색은 시간 복잡도 O(log(n))을 가지는 효율적인 탐색 방법이라고 할 수 있다.

효율적인 탐색을 하기 위해서 맨 처음 탐색 구간을 적절하게 설정하는 것도 중요하다.

 

문제는 앞에서 부터 순차적으로 담아야 하므로 특정 블루레이 길이를 가지고 앞에서 부터 꾹꾹 눌러담으며 몇 개의 블루레이 개수로 강의들을 모두 담을 수 있는지 체크하면서 주어진 개수를 만족하는 블루레이의 최소길이의 값을 찾아나간다.

• 각 레슨의 길이 중 최대 길이보다 작은값으로 블루레이 길이를 설정하면 그 블루레이에 아에 강의를 못 담는 상황이 발생한다
• 예를들어 총 48시간의 강의를 4개의 블루레이를 담고 싶다면 블루레이 개당 길이는 최소 12가 되어야하는 건 맞지만, 레슨 길이중 16시간짜리가 있으면, 블루레이 탐색의 최소값은 16시간이 되어야 맞다. 탐색의 최댓값은 강의 시간의 총합으로 한다. 1개의 블루레이에 담을 수 있는 경우이다
• 두 최소 탐색 값과 최대 탐색 값에서 재귀를 이용한 이진 탐색을 시행하여 최적의 길이를 찾는다.
• 원하는 블루레이 개수를 맞추면서 블루레이 size를 줄일 수 있을 때 까지 이진 탐색을 시행한다. 

아래는 코드이다

 

package page186;
 
import java.io.*;
import java.util.*;
 
public class Example2343 {
    static int[] arr;
    static int key;
    static int n;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        key = Integer.parseInt(st.nextToken());
        arr = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int max = arr[0];
        int total = 0;
        for(int i = 0; i<n; i++){ //각 레슨 중에서 최대값을 찾고, 레슨 시간의 총합을 구한다
            total += arr[i];
            if(max < arr[i])
                max = arr[i];
        }
 
       System.out.println(BinaryS(max ,total));
    }
 
    public static int BinaryS(int lo, int hi) { //이진 탐색으로 최소의 블루레이 길이를 구하는 메소드.
        if (lo > hi)
            return lo;
        int mid = (lo + hi) / 2;
        int count = getCount(mid);
 
        if (count > key) //원하는 블루레이 수보다 더 많이 나오면 블루레이 size를 늘리기 위해 우측 탐색
            return BinaryS(mid + 1, hi);
        else //원하는 key값 보다 작거나 같으면 블루레이 size를 줄이기 위해 좌측 탐색
            return BinaryS(lo, mid - 1);
    }
 
    public static int getCount(int size) { //해당 사이즈로 레슨 영상을 받았을 때 몇 개의 블루레이가 필요한지 세는 메소드
        int count = 0;
        int sum = 0;
        int i = 0;
        while (i < n) {
            if (sum + arr[i] <= size) {
                sum += arr[i];
                i++;
            } else {
                sum = 0;
                count++;
            }
        }
        count++;
        return count;
    }
}

문제의 파악이 쉽지 않은 문제이다.

어떻게 count를 해야 올바른 방법인가 고민이 많았지만, 오랫동안 생각해보니

블루레이 개수를 줄이길 원하고 뒤에서 담는 수고를 덜으려면 앞에서 순차적으로 담을 때 최대한 채울 수 있을 떄까지 강의를 눌러담는게 맞다.