[백준 2110 - Node.js] 공유기 설치

🔗 문제 링크

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

2110번: 공유기 설치

✏️ 풀이

const [N, C, ...coord] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split(/\s/)
  .map(Number);
coord.sort((a, b) => a - b);

const isPossible = (distance) => {
  let count = C - 1;
  let prevCoord = coord[0];
  for (let i = 1; i < coord.length; i++) {
    if (coord[i] - prevCoord >= distance) {
      count--;
      prevCoord = coord[i];
    }
  }
  return count <= 0;
};

let low = 1;
let high = coord[coord.length - 1];
while (low <= high) {
  const mid = Math.floor((low + high) / 2);
  if (isPossible(mid)) {
    low = mid + 1;
  } else {
    high = mid - 1;
  }
}

console.log(high);

가장 인접한 두 공유기 사이의 거리를 이분탐색을 통해 변경해가면서 C개의 공유기를 모두 설치할 수 있는 최대의 거리를 찾아내면 된다.

 

isPossible 함수는 주어진 거리를 기준으로 좌표상의 집에 C개의 공유기를 모두 설치할 수 있는지 여부를 반환한다. 이분탐색을 하면서 주어진 거리를 기준으로 C개의 공유기를 모두 설치할 수 있으면 거리를 더 증가시켜서 다시 시도해보고, 반대로 모두 설치할 수 없으면 거리를 더 감소시켜서 다시 시도해본다. 이 과정을 반복하면서 결국 C개의 공유기를 모두 설치할 수 있는 최대의 거리를 구할 수 있게 된다.