[백준/java] 2805번 나무자르기 , 이분탐색 알고리즘

- 문제 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

- 분류 : 이분탐색

 

이분탐색 (Binary Search)

이분탐색 알고리즘은 linear search에서 업그레이드된 방식으로, 정렬된 리스트를 반으로 나눠서 반복 탐색하는 방식이다.

계속 탐색범위를 반으로 나누므로 시간복잡도는 O(logN)이다.

 

---

백준2805번 나무자르기 풀이

• 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. => 상근이가 나무를 집에 가져가지 못할 경우는 없다. (즉 탐색했을 경우 찾는 값이 없는 경우는 없다)
  • if(first > last) return null;  not found 인 경우는 없다.
• 나무의 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다 => 가져갈 나무의 높이의 합을 구할 때 int 범위를 초과할 수 있으므로 result는 long타입으로 설정한다. 
  • int형 저장범위 : -2,147,483,648 ~ 2,147,483,647
• 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. => (나무의 높이 - h)가 음수인 경우는 잘리지 않기 때문에 result에 더하지 않는다. 
• 0부터 최대 나무의 높이를 범위로 두고, 이분탐색으로 절단기에 설정할 수 있는 높이의 최댓값을 구한다.
  • 만약 result < m 이면 더 잘라야하므로 왼쪽 범위를 탐색한다 (좀더 자르려면 절단기의 높이가 낮아져야 한다)
  • result > m 이면 덜 잘라야하므로 오른쪽 범위를 탐색한다 (좀덜 자르려면 절단기의 높이를 높혀야 한다)

나무자르기 예제

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

public class BOJ2805 {

    static int[] trees;

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        trees = new int[n];
        for (int i = 0; i < n; i++) {
            trees[i] = sc.nextInt();
        }

        int first = 0;
        int last = Arrays.stream(trees).max().getAsInt(); //최대 높이의 나무
        int middle = (last + first) / 2;
        long result = findResult(middle);

        while (first <= last) {
            if (result < m) {
                // 더 조금 잘라야 하니 왼쪽으로
                last = middle - 1;
            } else {
                // 더 많이 잘라야 하니 오른쪽으로
                first = middle + 1;
            } 

            middle = (last + first) / 2;
            result = findResult(middle);
        }
        System.out.println(middle);
    }

    public static long findResult(int h) {
        long result = 0;
        for (int tree : trees) {
            //음수인 경우는 더하지 않는다
            result += (Math.max((tree - h), 0));
        }
        return result;
    }
}

 

 

---

나무자르기 테스트케이스

1 1
1000000000
output : 999999999

5 100
99 1 1 1 1
output : 0