[백준 2805] 나무 자르기 (Java)

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

2805번: 나무 자르기

 

 

접근 방식

이분 탐색을 이용해 접근해야 시간초과가 나지 않는다.

 

아무리 길게 절단한다고 해도, 최대 입력 받은 나무 길이 중 가장 긴 길이만큼까지만 절단할 수 있다. (end = max in trees)

0부터 end를 시작으로 이분탐색을 진행한다.

 

예제로 예를 든다면

먼저 0과 20의 중간인 10을 먼저 생각해보자

 

10m(mid)를 자르게 되면 얻게 되는 길이는 (20 - 10) + (15 - 10) + (10 - 10) + (17 - 10) = 22로 목표인 M(=7)보다 크다.

이렇게 M < mid인 경우에는 높이를 올려서 잘려나가는 부분을 줄여야 한다.

다시 이분 탐색을 들어가는데 11과 20의 중간인 15를 고려한다.

(반대로 M > mid인 경우에는 0과 9를 고려)

 

위와 같은 경우를 반복한다. 언제까지? start가 end를 넘어갈 때까지(start > end라는 경우는 탐색이 끝났다는 것)

 

 

소스 코드

import java.util.Scanner;

public class Main {
    private static int N;
    private static int M;
    private static int[] trees;
    private static long max = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();

        trees = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            trees[i] = scanner.nextInt();
            max = Math.max(max, trees[i]);
        }

        long start = 0;
        long end = max;

        while (start <= end) {
            long mid = (start + end) / 2;
            long sum = 0;

            for (int tree : trees) {
                if (tree > mid) {
                    sum += tree - mid;
                }
            }

            if (sum >= M) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        System.out.println(end);
    }
}