[BJ] 2805 - 나무 자르기

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 백준 2085번 문제인 나무 자르기에 대해 알아보겠습니다.

 

 

 

접근 방법

해당 문제는 자른 후 남는 나무의 길이가 최소가 되도록 나무들을 자르는 문제입니다. 따라서 절단 높이는 최대한 높아야 합니다. 단순하게 제일 높은 나무 높이부터 0까지 1cm단위로 테스트해봐도 됩니다만.. 문제는 역시 시간복잡도입니다. 따라서, 탐색에서 시간복잡도가 $n\log{n}$인 이진 탐색을 사용합니다.

제가 생각하는 키 포인트들은 다음과 같습니다.

• 이진 탐색 : divide and qonquer를 이용한 탐색입니다. 대표적으로는 병합 정렬(merge sort), 퀵 정렬(quick sort)이 있습니다.
• 재귀 : 이진 탐색이라면 자연스럽게 따라오는 녀석입니다.

 

 

풀이 코드 (javascript)

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let woodsNumber = 0;
let woods = [];
let requiredLength = 0;
let max = 0;

function getRemain(woods, cutHeight) {
    return woods.reduce((acc, wood) => acc + (wood > cutHeight ? wood - cutHeight : 0), 0);
}

function findMaxHeight(woods, requiredLength, min, max, cutHeight) {
    // 중간 높이를 구합니다
    const middle = Math.floor((min + max) / 2);
    // 커팅 높이가 두번 연속 동일한 경우, 원하는 나무 길이가 맞아 떨어지지 않는 경우입니다
    // 따라서 반환합니다
    if(middle === cutHeight) return middle;

    const remain = getRemain(woods, middle);
    // 너무 많이 자른 경우
    if (remain > requiredLength) return findMaxHeight(woods, requiredLength, middle, max, middle);
    // 너무 짧게 자른 경우
    else if (remain < requiredLength) return findMaxHeight(woods, requiredLength, min, middle, middle);
    // 딱 맞게 자른 경우
    else return middle;
}

rl
    .on("line", function(line) {
        if (woodsNumber === 0) [woodsNumber, requiredLength] = line.split(" ").map(wood => parseInt(wood, 10));
        else {
            woods = line.split(" ").map(wood => {
                const parsedWood = parseInt(wood, 10);
                // 최대 길이를 구합니다
                if(parsedWood > max) max = parsedWood;
                return parsedWood;
            });
            rl.close();
        }
    })
    .on("close", function() {
        console.log(findMaxHeight(woods, requiredLength, 0, max));
        
        process.exit();
    });

나무들의 길이를 입력 받을 때, 최대 길이를 구합니다. (입력 받은 후 정렬을 쓰면 시간이 오버될거 같아서..)

다 받으면 woods에 대해, 최소(0)과 최대(max)의 중간을 커팅 높이로 정합니다. 이렇게 잘라본 후, 너무 많이 잘렸다면 커팅 높이를 높이고, 너무 적게 잘랐다면 커팅 높이를 낮춥니다. 원하는 나무 길이가 딱 맞아 떨어지지 않을 수 있으므로, 커팅 높이가 두번 연속으로 같다면 해당 높이를 반환하도록 예외처리도 해줍니다.

이렇게 반복하여 적절한 커팅 높이를 찾습니다.