[백준/JAVA] 2805번 : 나무 자르기 (이분탐색)

문제 풀러 가기 -> https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

입력

첫번째 줄을 보자.

N은 나무 개수이다. N = 4

M은 필요한 나무의 길이이다. M = 7

두 번째 줄은 각 나무의 길이이다.

---

풀이

절단기를 몇 m로 설정하고 나무를 베었을 때, 필요한 나무의 길이를 충족하면서 절단기의 높이를 최대가 될 것인가?

절단기의 높이를 설정하면, 그 높이보다 작은 나무는 잘리지 않을 것이고, 절단기 높이보다 큰 나무는 (나무 높이 - 절단기 높이) 만큼이 잘릴 것이다.

cutting()

static long cutting(int height){
    long result = 0;
    for(int i=0;i<trees.length;i++){
        if(trees[i] > height){
            result += trees[i] - height;
        }
    }
    return  result;
}

나무 높이 배열과 절단기의 높이를 매개변수로 전달하면 얻을 수 있는 총 나무 길이를 반환한다.

이분탐색

while(min<max){
    int mid = (min+max)/2;
    long sum = cutting(mid);

    if(sum < M){
        max = mid;
    }else{
        min = mid+1;
    }
}

일반적인 이분탐색과 유사하지만 주의해야 할 점이 있다.

만약 cutting()의 반환 값이 M(필요한 나무 길이) 보다 작으면 절단기의 높이를 높이는 것이 아니라 낮춰야 한다.

절단기의 높이가 높아질수록 cutting()의 반환 값은 작아지기 때문이다.

1. mid(중간값)을 설정한다.
2. cutting(mid)로 현재 절단기의 높이로 잘랐을 때 얻을 수 있는 나무의 길이를 구한다. (long sum = cutting(mid);
3. 만약 sum이 M보다 작으면 max = mid로 범위를 아래로 내린다.
4. 만약 sum이 M보다 크거나 같으면 min = mid+1로 범위를 위로 높인다.

마지막에 min이 max보다 커지면 종료된다.

그러나 마지막에 종료될 때 M이 sum과 같아지면 min이 +1되며 종료하기 때문에, 원하는 탐색 값에 +1이 된 채로 종료되게 된다. 따라서 마지막에 출력할 때는 -1 한 값을 출력해야 한다.

---

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class No2805 {
    static int[] trees;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        trees = new int[N];
        int max = 0;
        int min = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            max = Math.max(trees[i],max);
        }

        //이분탐색
        while(min<max){
            int mid = (min+max)/2;
            long sum = cutting(mid);

            if(sum < M){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        System.out.println(min-1);
    }
    static long cutting(int height){
        long result = 0;
        for(int i=0;i<trees.length;i++){
            if(trees[i] > height){
                result += trees[i] - height;
            }
        }
        return  result;
    }
}