[백준] - 2110 공유기 설치 (node.js)

문제링크

풀이

이분탐색으로 풀었다. 공유기 사이의 거리(mid)에 따라 공유기의 수를 세고 주어진 공유기 개수보다 작다면 end를 줄이고 크다면 start를 늘리는 식으로 풀었다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, c] = input.shift().split(" ").map(Number);
let home = [];
input.forEach((a) => home.push(Number(a)));
home.sort((a, b) => a - b);

let start = 1;
let end = home[n - 1] - home[0] + 1;

while (start <= end) {
  let mid = ~~((start + end) / 2);

  let cnt = 1;
  let lastlo = home[0];
  for (let i = 1; i < home.length; i++) {
    let lo = home[i];
    if (lo - lastlo >= mid) {
      cnt++;
      lastlo = lo;
    }
  }

  if (cnt >= c) {
    start = mid + 1;
  } else {
    end = mid - 1;
  }
}

console.log(end);