[백준] - 17266 어두운 굴다리 (node.js)

문제링크

코드

// 어두운 굴다리

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

const n = Number(arr[0]);
const m = Number(arr[1]);
const garo = arr[2].split(" ").map(Number);

const isPossible = (mid) => {
  // 처음위치 - 0 < mid
  if (garo[0] > mid) return false;
  // 가로등1 - 가로등2 < mid * 2
  for (let i = 1; i < m; i++) {
    if (garo[i] - garo[i - 1] > mid * 2) return false;
  }
  // 길의 길이 - 마지막가로등 < mid
  if (n - garo[m - 1] > mid) return false;
  return true;
};

let start = 1;
let end = n;

let h = n;

while (start <= end) { // 이진 탐색
  mid = Math.floor((start + end) / 2);

  if (isPossible(mid)) {
    h = mid;
    end = mid - 1;
  } else {
    start = mid + 1;
  }
}

console.log(h);

이진 탐색으로 풀었다. 어떤 식으로 풀어야할지 감이 잡히지 않아서 밑에 힌트를 보고 풀었는데, 일주일 쯤 뒤에 다시 풀어봐야할 것 같다.