[boj] 2805. 나무 자르기 (node.js)

문제 요약

BOJ 2805 나무 자르기

풀이

• 이분탐색 알고리즘을 구현한다.
• 이때 L, R을 한 칸씩 이동하기 위한 내부 조건으로 해당(mid)부터 나무를 잘랐을 때 원하는 값보다 크거나 같으면 1, 작으면 0을 반환하는 bool 함수를 활용한다.

내 풀이

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

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const [N, M] = input().split(" ").map(Number);
  const arr = input().split(" ").map(Number);
  arr.sort((a, b) => a - b);
  binarySearch(0, 2000000000);

  function binarySearch(L, R) {
    let result = R;
    while (L <= R) {
      let mid = Math.trunc((L + R) / 2);
      if (sumTreeLen(mid)) {
        result = mid;
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    console.log(result);
  }

  function sumTreeLen(start) {
    let sum = 0;
    arr.forEach((elem) => {
      if (elem > start) sum += elem - start;
    });
    return sum >= M;
  }
});

• L, R에 초기값을 줄 때 R에 최대 나무의 요구 길이인 2000000000을 주어야 한다.