[99클럽 코테 스터디 TIL#6일차] 백준 2805 나무자르기

문제

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

 

 

문제풀이

탐색 공간 범위도 문제가 알아서 지정해줬고, 식 세우는 것도 쉬웠다.

문제에서 식 세우는 것을 어렵게 꼬아낼 때, 이분탐색 난이도가 급격하게 올라가는 것 같다.

 

 

작성한 코드

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        
        long[] tree = new long[n];
        
        for(int i = 0; i < n; i++) {
            tree[i] = sc.nextLong();
        }
        
        long left = 0;
        long right = 1000000000;
        long answer = 0;
        
        while(left <= right) {
            long mid = (left + right) / 2;
            long guessM = 0;
            
            for(long height : tree) {
                long remain = height - mid;
                if( remain > 0) {
                    guessM += remain;
                }
            }
            
            if(guessM >= m) {
                answer = Math.max(answer, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        System.out.println(answer);
    }
}