BOJ] 2805. 나무 자르기

BOJ]2805.나무 자르기

 

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

2805번: 나무 자르기

 

이분탐색(Binary Search) 문제.

.

0부터 나무의 가장 높은 높이를 찾아서 그 사이의 값들을 전기톱의 높이로 지정해가면서 값을 구하는 과정.

이분탐색의 시작점 left와 right는 

left는 0 / right는 나무의 가장 좋은 높이로 지정.

 

1.  N개의 나무를 입력받을 때, 가장 높은 나무를 기억(max)

2. 이분탐색을 위한 범위는 0부터 max까지임.

3. 이분탐색의 시작지점 left=0  , right=max

4. 이분탐색의 내부조건은 mid 기준으로 잘랐을 때 가져갈 수 있는 나무의 합이 내가 가져가야하는 나무의 길이(M)와 비교한다,

4-1.  잘라낸 나무의 합이 M보다 작다면, mid를 왼쪽으로 이동시켜야 하므로, right의 값 조정.

4-2. 잘라낸 나무의 합이 M보다 크다면, mid를 오른쪽으로 이동시켜야 하므로, left의 값 조정.

.

.

package beakjoon;
 
import java.util.Scanner;
 
public class bj_2805_나무자르기 {
 
    static int N;
    static int M;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //나무의 수 
        N = sc.nextInt();
        arr = new int[N];
        //가져가야하는 나무의 길이 
        M = sc.nextInt();
        int max=Integer.MIN_VALUE;
        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max, arr[i]);
        }
        long left=0;
        long right = max;
        long res=0;
        
        while(left<=right) {
            long mid = (left+right)/2;
            long total =0;
            for(int i=0; i<N; i++) {
                if(mid<arr[i]) {
                    total += arr[i] - mid; 
                }
            }
            if(total >= M) {
                res=mid;
                left = mid+1;
            }
            else {
                right = mid-1;
            }
        }//end while loop
        System.out.println(res);
    }
}