백준[node.js] > 2805번 나무 자르기

 

문제링크

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

문제풀이

문제조건을 보고 이분탐색이라는 느낌을 받았다. ( 아래조건 참고 )

만약 이분탐색을 하지 않고 나무 높이를 하나씩 낮추면서 최댓값을 구하려면 괴랄한 연산횟수가 나온다. 

하지만 이분탐색으로 탐색하면 계산횟수를 획기적으로 많이 줄일 수 있다. 이렇게 획기적으로 줄어드는 이유는 나무 높이의 범위가 너무 크기 때문이다. -> 이부분은 직접 케이스를 산정해서 테스트해보면 알 수 있다. )

 

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

let [N, M] = input[0].split(" ").map((n) => Number(n));

let line = input[1].split(" ").map((n) => Number(n));
let max = Math.max(...line);
let [left, right] = [0, max];
let mid = Math.floor((left + right) / 2);

while (left !== mid) {
    let treeLength = 0;

    line.forEach((height) => {
        if (height > mid) {
            treeLength = treeLength + height - mid;
        }
    });
    if (treeLength >= M) {
        left = mid;
        mid = Math.floor((left + right) / 2);
    } else {
        right = mid;
        mid = Math.floor((left + right) / 2);
    }
}

console.log(mid);