[Java] 이진 탐색 (나무 자르기)

나름대로 Time Complexity를 생각해서 배열을 정렬하고 첫 번째 인덱스의 나무와 두 번째 인덱스의 나무의 차를 계산하면서 총합을 더해갔는데 계속 틀려서 다른 방법을 생각했다.

 

배열을 정렬하지 않고 이진탐색을 이용하는 방법인데, 주어진 배열과 수가 커서 알맞은 방법인 것 같다.

 

나무 중에서 가장 길이가 긴 나무의 높이를 top, 바닥을 down으로 두고 위아래로 이진 탐색을 진행한다.

 

만약 높이가 middle일 때 모든 (나무 높이-middle)의 합이 구하고자 하는 높이와 같다면 답이 구해진다.

 

위와 같이 숫자가 정확히 나누어 떨어지지 않는다면 middle이 아니고 middle-1이 답일 것이다. 

 

숫자의 범위가 매우 클 떄 이진탐색을 고려해 보자.

 

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

2805번: 나무 자르기

 

 

 

 

 

 

 

public class Main {

    static int N, M;
    static Integer[] array;
    static long  sum = 0;
    static int top=0, down=0, middle;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        array = new Integer[N];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st2.nextToken());
        }

        binarySearch();

        System.out.println(top);
    }



    public static void binarySearch() {

        for(int i : array) top = Math.max(i,top); //배열에서 최대값 구하기

        while (down <= top) {
            sum = 0;
            middle = (down + top) / 2;

            for (int i = 0; i < N; i++) { // middle 보다 키가 큰 나무들만
                if (array[i] > middle)
                    sum += (array[i]-middle);
            }

            if (M == sum)
                { System.out.println(middle); exit(0); }
            else if (M < sum)
                down = middle + 1;
            else
                top = middle - 1;

        }
    }

}