[Algorithm/Java][백준] 2805번 나무 자르기

[백준] 2805번 나무 자르기

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

문제접근

처음에는 감이 안잡혀서 밑에 알고리즘 분류가 이분 탐색이라고 써져있어서, 옛날에 배운 기억으로 코드를 작성했다.
left, right, mid를 이용해서 값을 찾았다.
만약 딱 떨어지는 값이 없을 경우, 적어도 m을 넘겨야하기 때문에 right값을 return하도록 했다.

Code

import java.util.Arrays;
import java.util.Scanner;

public class BOJ2805 {

    static int cutHeight(int[] trees, int m){
        Arrays.sort(trees);
        int left = 0;
        int right = trees[trees.length-1];
        while(left <= right){
            long sum =0;
            int mid = (left + right) / 2;
            for(int tree : trees){
                if(tree-mid > 0) sum += tree-mid;
            }
            if(sum > m) left = mid +1;
            else if(sum < m) right = mid-1;
            else{
                return mid;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] trees = new int[n];
        for (int i = 0; i <n ; i++) {
            trees[i] = sc.nextInt();
        }
        System.out.println(cutHeight(trees,m));
    }
}

어려웠던 점 / 배운 점 / 느낀 점

일단 이분 탐색이 정확히는 기억이 나지가 않았고 이런 느낌이였지 하고 풀어서 처음에는 left = mid +1, right = mid-1 을 그냥 mid값만 대입해서 무한루프가 돌았다. 기본적인 알고리즘은 한 번 정리하면서 공부할 필요성을 느꼈다.