[백준]2805 - 나무 자르기 문제 풀이(Java,자바)

2805번: 나무 자르기

들어가며

이 문제는 랜선 자르기 문제와 유사하다.

[백준]1654 - 랜선 자르기 문제 풀이(Java,자바)

[백준]1654 - 랜선 자르기 문제 풀이(Java,자바)

 

이분 탐색을 이용하면 시간 초과가 나지 않고 풀 수 있다.

코드

package solved.ac.class3;

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

public class 백준2805_나무자르기 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = reader.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        int[] trees = Arrays.stream(reader.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        Arrays.sort(trees);
        int start = 0;
        int end = trees[trees.length - 1];
        long result = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            long temp = count(trees, mid);

            if (temp >= m) {
                result = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.println(result);
    }

    static long count(int[] trees, int sawHeight) {
        long result = 0;
        for (var tree : trees) {
            if (tree < sawHeight) {
                continue;
            }
            result += tree - sawHeight;
        }
        return result;
    }
}

풀이

M 보다 크거나 같은 값을 찾기 위해서 여러 경우의 수를 탐색한다.

탐색하는 방법으로 이분 탐색을 사용한다.

당연하게도 시간 복잡도가 일반 브루트 포스보다 작기 때문이다.

 

이분 탐색을 위해서 먼저 오름차순으로 정렬한다.

가지고 있는 나무 중 가장 긴 값을 M 범위의 끝으로 하고 진행한다.

 

여기서 중요한 것은 현재 mid로 얻을 수 있는 나무의 개수인 temp을 M하고 크거나 같은 지 비교하고

크거나 같은 경우  result를 mid로 변경해야 한다.

왜냐하면, 반드시 m으로 떨어지지 않는 경우가 존재하기 때문이다.

 

 

위와 같은 로직을 예시로 설명하면 다음과 같다.

 

n = 4, m =7
20 15 10 17

입력 시에 오름차순 정렬을 진행한다.

10 15 17 20 이 된다.

 

그러면 시작점을 0, 끝점을 20으로 시작한다.

중간값은 10

절단기의 높이를 10으로 설정하고 얻을 수 있는 나무 길이를 계산해본다.

그러면 총 12m를 얻게 된다. m보다 크므로 일단 result에 12를 저장하고 절단기의 높이를 올린다.

 

시작점을 10 끝점을 20으로 한다.

절단기의 높이를 15로 설정하고 얻을 수 있는 나무 길이를 계산한다.

그러면 총 7m 이다.

m과 같으므로 끝이 난다.