BOJ02805 나무 자르기

https://www.acmicpc.net/problem/2805 (opens new window)

상근이는 나무 M미터가 필요하다.

모재 절단기는 다음과 같이 동작한다. 상근이는 절단기의 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 높이가 H보다 큰 나무는 H 위 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.

나무는 필요한 만큼 집에 가져가려 한다. 적어도 M미터의 나무를 집에 가져가기 위해서 잘단기에 설정할 수 있는 높이의 최댓값을 구한다.

이분 탐색

배열 내부의 데이터가 정렬되어 있으면, 탐색 범위를 좁혀가며 데이터를 탐색한다.

이진 탐색의 위치를 나타내는 변수 3개 시작점, 끝점, 중간점이 필요하다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복 비교하여 데이터를 검색한다.

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(logN) 이다. 이진 탐색을 구현하는 방법은 1. 재귀 함수와 단순 반복문을 이용하는 방법이다.

제출 코드

나무 자르기 문제는 탐색하고자 하는 인덱스의 값을 구하는 것이 아니라 톱의 길이를 줄여가며 가장 최적의 해가 될 때는 찾는 것이기 때문에 정렬 과정이 생략되어도 지장이 없다.

매번 mid 값을 갱신한 후 모든 배열의 원소를 확인한다.

long total = 0;
int mid = (start + end) / 2;
for (int i = 0; i < n; i++) {
    if (heights[i] > mid) {
        total += heights[i] - mid;
    }
}

아래는 반복문을 사용하여 구현한 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2805 {

    static int n, m;
    static int[] heights;

    private static int binarySearch(int start, int end) {
        int result = 0;
        while (start <= end) {
            long total = 0;
            int mid = (start + end) / 2;
            for (int i = 0; i < n; i++) {
                if (heights[i] > mid) {
                    total += heights[i] - mid;
                }
            }

            if (total < m) {
                end = mid - 1;
            } else {
                result = mid;
                start = mid + 1;
            }
        }

        return result;
    }

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

        n = scanner.nextInt(); // 나무의 수
        m = scanner.nextInt(); // 가져갈 나무의 길이

        heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextInt();
        }

        System.out.println(binarySearch(0, 1_000_000_000));
    }
}

#algorithm #BOJ #이분 탐색