[백준1477_자바스크립트(javascript)] - 휴게소 세우기

🔴 문제

휴게소 세우기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m, l], inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const location = [0, ...(inputs ?? []), l].sort((a, b) => a - b);
const diff = [];

for (let i = 0; i <= n; i++) {
  diff.push(location[i + 1] - location[i]);
}

let start = 1;
let end = l - 1;

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

  for (const d of diff) {
    cnt += Math.floor((d - 1) / mid);
  }

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

console.log(start);

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 휴게소 간의 최대 거리를 이분탐색으로 찾으면 된다.

첫 예시에서 휴게소는 아래와 같이 세워져 있다.

0(시작지점) 82, 201, 411, 555, 722, 755, 800(끝지점)

다음 휴게소 간의 간격을 다시 구해준다.

82, 119, 210, 144, 67, 133, 45

만약 휴게소가 아예 없다면, 시작위치-끝위치 간격이 하나가 들어갈 테니까,
이론상 가능한 휴게소 간의 간격은 1부터 끝위치-1이다.

즉 1, 799 로 이분탐색을 수행해 중앙값인 400을 구한 뒤, 모든 간격을 400으로 나눴을 때 휴게소를 몇 개 더 세워야 하는지를 찾는 문제다.

위의 간격에서는 400으로 나눴을 때 휴게소를 0개 세울 수 있으므로 끝 값을 399로 업데이트 한 뒤 다시 이분탐색을 진행해 정답인 70을 찾아야 하는 문제다.

다만 조금 까다로운 점은 휴게소를 세워야 하는 위치를 고려해야 하기 때문에 d-1/mid를 수행해야 한다는 점이다.
또한 아래처럼 어떤것을 정답으로 놓고 최소화할 지 생각하는 게 까다로웠다는점에 동의한다.

더 열심히 해야겠다.

🔵 Ref