[백준] 나무 자르기

백준 2805번

 

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

2805번: 나무 자르기

 

프로그래머스 징검다리 건너기 문제를 풀고 이분 탐색이 입력값을 줄이고 문제를 최적화하는데 매우 좋다는 것을 알게 되었다.

입력값을 O(logN)해서 시간복잡도가 매우 줄어들게 된다.

 

분석

나무 자르기는 이분 탐색을 이용해서 풀어야하는 문제 중 하나이다. 결정 문제이고 Check(x)에서 x의 값에 따라 적어도 M미터의 나무를 집에 가지고 갈 수 없기 때문이다.

x는 절단 설정 높이로 15미터의 나무라고 했을 때, x를 12미터로 설정하면 집에 가지고 갈 수 있는 나무는 3미터이다.

 

그래서 M을 7미터라고 하고 20, 15, 10의 나무를 자를 수 있다고 할 때 x를 14미터로 설정할 경우 6미터, 1미터 해서 총 7미터를 가지고 갈 수 있다. 혹시라도 x를 15미터라고 한다면, 총 5미터의 나무만 집에 가져갈 수 있다.

 

이분적인 측면으로 집에 가져갈 나무가 M미터가 되냐 안되냐의 문제로 보면 될 것 같다.

 

입력값은 아래와 같이 무려 10억이다. 

따라서 이분 탐색을 위해 lo와 hi를 정해보자면 lo = 0, hi = 1,000,000,000가 될 것 같다.

 

정답 코드

import java.io.*;
import java.util.stream.Stream;

public class Main2805 {
    static int N, M, max = 0;
    static int[] trees;
    public static void main(String[] args) throws IOException{
        int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        trees = Stream.of(input).mapToInt(Integer::parseInt).toArray();

        int lo = 0, hi = 1000000000, mid;
        while(lo <= hi) {
            mid = (lo + hi) / 2;
            if (check_tree(mid)) {
                lo = mid + 1;
                if (answer < mid) {
                    answer = mid;
                }
            } else {
                hi = mid - 1;
            }
        }
        System.out.println(answer);
    }

    public static boolean check_tree(int mid) {
        int t = 0;
        for(int i = 0; i < N; i++) {
            if (trees[i] <= mid) continue;
            t += (trees[i] - mid);
            if (t >= M)
                return true;
        }
        return false;
    }
}

 

느낀 점

이분 탐색은 먼저 조건이 무엇인지 아는 게 제일 중요하다.

조건이 무엇인지를 알고 나면 x가 무엇이고 x가 어떻게 이분적으로 나뉘어지는지를 알게 되는 것 같다.

 

나무 자르기 문제는 비교적 쉽게 조건과 x를 찾을 수 있었다. 좀 더 다양한 이분 탐색 문제를 풀어보면 좋을 것 같다.