나무 자르기

풀이

 이 문제는 이분 탐색(파라매트릭 서치) 유형의 문제다. 만약 이분 탐색(파라매트릭 서치)을 사용하지 않고 순차 탐색을 사용한다면 시간 복잡도는 O(NH)가 된다. 1 ≤ N ≤ 1,000,000, 0 ≤ H ≤ 1,000,000,000 이므로 연산 결과가 1,000조가 나오므로 시간초과 판정이 뜬다.
 이분 탐색을 사용하기 위해 범위를 설정하자. min=0, max="나무의 가장 높은 값"으로 설정하고 mid를 조정해가면서 가능한 H의 최대값을 구하면 된다. 이분 탐색을 활용한 코드의 시간 복잡도는 O(NlogH)로 대략 3천만이 나오므로 문제를 해결할 수 있다.
 또한 단일 나무의 길이가 최대 1,000,000,000 (10억) 이기 때문에 합산하는 과정에서 overflow가 발생하지 않도록 sum 변수는 int 타입이 아닌 long 타입으로 지정해줘야 한다.

시간 복잡도 : O(NlogH) (최대 30,000,000의 연산)

Java

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        int max_value = Integer.MIN_VALUE;
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            max_value = Math.max(max_value, arr[i]);
        }

        int lt = 0;
        int rt = max_value-1;
        int result = Integer.MIN_VALUE;
        while (lt<=rt){
            int H = (lt+rt)/2;
            long sum = 0;
            for(int i=0; i<N; i++){
                if(arr[i]>H)
                    sum += arr[i]-H;
            }
            if(sum>=M){
                result = Math.max(H, result);
                lt = H+1;
            }
            else{
                rt = H-1;
            }
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}