[BOJ 2805] 나무 자르기 (Java)

문제

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

2805번: 나무 자르기

 

풀이

절단기의 설정할 수 있는 높이로 이분 탐색을 하여 풀었다. 예제를 그려보면 다음과 같다 

적어도 7미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제이다. 

최초 시작과 끝을 아래와 같이 설정한 후, 이분 탐색을 진행하여 답을 구할 수 있다.

절단기에 설정할 수 있는 최소 H: 0

절단기에 설정할 수 있는 최대 H: 20

mid값 높이로 나무를 절단 시 필요한 M길이 이상인지 미만인지에 따라서 right, left 값을 갱신해 준다.

 

유사 문제

2021.11.29 - [Problem Solving/BOJ] - [BOJ 2110] 공유기 설치 (Java)

[BOJ 2110] 공유기 설치 (Java)

 

소스코드

package binarysearch;

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

public class BOJ2805 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 나무의 수
        long M = Long.parseLong(st.nextToken()); // 필요한 나무의 길이

        long[] tree = new long[N];

        long left = 0;
        long right = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            tree[i] = Long.parseLong(st.nextToken());
            right = Math.max(right, tree[i]);
        }
        Arrays.sort(tree);

        long answer = 0;
        while(left <= right){
            long mid = (left+right)/2;
            if(getMeter(mid, tree) >= M){
                // 자른 나무길이가 필요한 나무 길이보다 같거나 큰 경우
                // H를 높여서 덜 잘라야 함
                answer = Math.max(mid, answer);
                left = mid+1;
            } else {
                // 자른 나무길이가 필요한 나무 길이보다 작은 경우
                // H를 낮춰서 더 많이 잘라야 함
                right = mid-1;
            }
        }
        System.out.println(answer);
    }
    public static long getMeter(long H, long[] tree){
        long ans = 0;
        for(int i = tree.length-1; i >= 0; i--){
            long t = tree[i];
            if(t <= H) break;
            ans += (t-H);
        }
        return ans;
    }
}