백준 2805번 나무 자르기 Node.js 풀이

문제 링크

- 풀이

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

const [N, M] = input.shift().split(" ").map(Number);

const arr = input[0]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);

let start = 1;

let end = arr[arr.length - 1];

let answer = 0;

while (start <= end) {
  const mid = Math.floor((start + end) / 2);

  let sum = 0;

  for (let x of arr) {
    if (x > mid) {
      sum += x - mid;
    }
  }

  // 만들어진 나무의 길이 합이 목표보다 짧다면,
  // 즉 나무 길이를 더 짧게 해주어서 늘려주어야한다
  if (M > sum) {
    end = mid - 1;
  }

  // 만들어진 나무 길이 합이 목표값보다 많다면
  // 나무 길이를 더 늘려주어서 sum이 작아지도록 해야한다.
  else {
    answer = mid;
    start = mid + 1;
  }
}

console.log(answer);

이 문제도 랜선 자르기 문제와 비슷하게, 해당 조건에 맞는 총합 (sum)값을 구해주고,

나무 길이를 조절해주어서 정답을 찾는 문제이다.