알고리즘) 나무 자르기(백준 이분탐색 2805번)

문제(백준)

 

 이분 탐색을 통해 최소한 M미터 이상의 나무를 가져갈 수 있는 상황을 모두 체크해야 한다. 단순 이분 탐색과 다른 점은 이분 탐색에서는 확인하고자 하는 배열을 정렬해서 모든 처리가 끝나지만, 이 문제처럼 배열의 순서가 지켜져야 하는 상황에서는 아래와 같이 Java Stream을 사용해 rt 값을 최댓값으로 정의할 수 있다. (lt 역시 최솟값으로 설정해야 한다.) 

 유의할 점은 조건에 일치하는 경우에 lt, rt를 어떻게 움직이냐는 것인데, 높이(mid)를 높게 잡을 수록 가지고 갈 수 있는 나무가 적어진다. 문제에서는 자르는 높이의 최댓값(가져갈 수 있는 양은 최솟값이 됨)을 구하기 때문에, sum이 M과 일치하거나 더 높은 경우에는 자르는 높이를 올려야 한다. 즉, 두 범위 중 뒷 범위에서 탐색이 다시 이루어져야 하기 때문에 lt가 mid + 1이 되어야 한다.

작성 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private int solution(int n, int m, int[] list) {
        int answer = 0;

        int lt = 1;
        int rt = Arrays.stream(list).max().getAsInt();

        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            long sum = 0;
            for (int x : list) {
                if (x - mid > 0) sum += (x - mid);
            }
            if (sum >= m) {
                lt = mid + 1;
                answer = mid;
            }
            else rt = mid - 1;
        }
        return answer;
    }

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) list[i] = sc.nextInt();

        System.out.println(main.solution(n, m, list));
    }
}

 

맞게 풀었는데도 계속해서 오답이라고 나올 경우 이러한 부분들을 눈여겨 보자.

1. 집으로 가져가고자 하는 나무의 값은 최대 2,000,000,000이다. 즉, 위 코드에서는 변수 sum이 해당 값과 같거나 더 많을 경우가 참인 경우인데, 이 sum은 4 byte 정수형 타입(int)으로 표현하지 못하는 수일 가능성이 있다. 그래서, 변수 sum은 int가 아닌 long 타입으로 정의해주는 것이 좋다. 이 부분 때문에 여섯번 가량을 오답 판정을 받았다..

2. 나무 높이의 합은 항상 M보다 크거나 같아서 늘 나무를 가져갈 수 있다고 했고, 각 나무의 높이는 0 혹은 양의 정수로 표현됨을 문제를 통해 알 수 있다. 즉, lt를 0으로 정의하기 쉽지만 1로 정의하는 것이 더 바람직하다.

3. 단순히 이분 탐색을 통해 특정 값을 찾으면 끝나는 것이 아니라 특정 값 '이상'이 되어야 하기 때문에 'sum > mid'인 경우와 'sum == mid'인 경우를 함께 확인해야 한다.