★ [백준][Java] 2805번 나무 자르기 (이진탐색)

틀렸습니다.

Line: 33의 wood변수(자른 나무들의 합)의 최대값은

N과 M의 최대값의 곱인 1,000,000 * 2,000,000,000가 될 수 있기 때문에 long으로 선언해주어야 한다

 

수행시간 1152ms -> 576ms

처음에 풀 때는 나무들 높이 배열(height)를  Arrays.sort(height) 해줬는데

그렇게 할 필요가 없음 어차피 모든 height를 전부 돌기 때문에

다만 그런 경우에는 이진탐색을 할 때 오른쪽 값인 int right의 초기값을 어떻게 설정해주느냐인데

기존에는 right = height[height.length-1]로 해줬지만

그럴 필요 없이 문제에서 제한사항에서 주어진 나무 높이의 최대값으로 하거나

Line:23에서 나무 높이들 입력해줄 때 최대값을 갱신시켜주면 된다

 

가장 ciritical한 실수는 int형의 최대값이 약 21억정도라는 것을 관과했다는 것

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        int M = stoi(str[1]);
        int[] height = new int[N];
        
        
        
        str = br.readLine().split(" ");
        for(int i=0; i<N; i++)
            height[i] = stoi(str[i]);
        
        int left = 0;
        int right = 2000000000;
        int mid = 0;
        int res = 0;
        
        while(left<=right) {
            mid = (left+right)/2;
            long wood = 0;
            
            for(int h : height)
                wood += (h-mid<=0)?0:h-mid;
        
            if(wood<M)
                right = mid-1;
            else{
                left = mid+1;
                res = mid;
            }
        }
        
        System.out.println(res);
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}