[바미] 나무 자르기

문제

 

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const trees = input[1].split(' ').map(Number);

function getMaxSawHeight(N, M, trees) {
    let low = 0;
    let high = Math.max(...trees);
    let result = 0;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const totalWood = trees.reduce((acc, height) => {
            if (height > mid) {
                return acc + (height - mid);
            } else {
                return acc;
            }
        }, 0);

        if (totalWood >= M) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result;
}

const maxHeight = getMaxSawHeight(N, M, trees);
console.log(maxHeight);

문제 해설

이 문제는 이진 탐색(Binary Search)을 활용하여 최적의 절단기 높이를 찾는 전형적인 문제입니다.

나무의 높이 값을 조정하면서 필요한 나무의 길이를 얻을 수 있는 최적의 절단기 높이를 찾아야 하죠.

 

그래서 최적의 절단기 높이를 찾는 과정은 아래와 같습니다.

 

절단기 높이를 이진 탐색을 통해 결정되는데 가능한 최소 높이(low)는 0, 최대 높이(high)는 가장 긴 나무의 높이로 설정합니다.
그 후 중간 높이(mid)를 계산하여 그 높이로 나무를 잘랐을 때 얻을 수 있는 나무 길이를 계산합니다.

이 때 얻은 나무 길이가 필요 나무 길이 M보다 크거나 같다면 더 높은 높이로 시도해보고, 그렇지 않다면 더 낮은 높이로 다시 시도합니다.

이 과정을 반복하며 최적의 높이를 찾도록 풀었습니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

이진 탐색의 시간 복잡도는 𝑂(log⁡ 𝐻)이며, 각 단계에서 모든 나무 높이를 합산하는 데 𝑂(𝑁)이 소요됩니다.

따라서 전체 시간 복잡도는 𝑂(𝑁 log⁡ 𝐻)이 됩니다. 여기서 𝐻는 가장 높은 나무의 높이를 의미하죠.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

공간 복잡도는 입력 데이터와 해시셋을 저장하는 데 필요한 O(N) 크기 입니다.

이진 탐색 과정에서 추가적인 메모리가 거의 필요하지 않기 때문에 전체 공간 복잡도는 O(N)이 됩니다.