• 정렬된 배열 / 오름·내림차순 보장

• 최솟값 / 최댓값 / 가능한 값 중 최대·최소

• ~할 수 있는가? / 조건을 만족하는지 판별

• 조건을 바탕으로 추론하는 경우 매개변수 탐색

• 정렬되어 있는 리스트에서, 탐색 번위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 시작점, 끝점을 명시하고 중간지점을 이용하여 탐색 범위 설정

• 로직 자체는 쉬운데, 접근 방법을 어떻게 해야할지 고민하는 문제들이 많음

• 그리디와 접목하는 등

function solution(n, times) {
  let left = 1;
  let right = Math.max(...times) * n;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    let count = 0;
    for (const time of times) {
      count += Math.floor(mid / time);
    }
    if (count >= n) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

• 문제의 범위가 괴랄함. 일단 일반적인 그리디로 하면 시간초과 나겠다 ⇒ 효율적 탐색방법 모색
• 다음으로는 접근방법에 대한 추론
  • 시간을 기준으로 탐색 범위 설정 ⇒ 최소 1초, 최대 max(time) * n을 도출 필요
  • 시간을 times 내부 time으로 나누었을때의 총 합이 n이 될 수 있다는 것을 추론 ⇒ 이게 젤 어려워 진짜
  • 이후 mid값을 기준으로 이분탐색 동작, 이때 count ≥ n보다 크다면 범위를 줄일 필요가 있다는 것이니 right = mid - 1;
  • 시간의 최소값을 구하는거니까 환

/*
구하는 값 => 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램
이분 탐색 기준 => 공유기 사이 거리
*/
const input = require("fs")
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n");
const [N, C] = input.shift().split(" ").map(Number);
const arr = input.map((item) => +item).sort((a, b) => a - b);
left = 1;
right = arr[N - 1] - arr[0];
while (left <= right) {
  let mid = Math.floor((left + right) / 2);
  let prev = arr[0];
  let count = 1;
  for (let i = 0; i < N; i++) {
    if (arr[i] - prev >= mid) {
      prev = arr[i];
      count++;
    }
  }
  if (count >= C) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
console.log(right);

• 그리디 처럼 보이지만 이분 탐색이 필요한 문제
• 공유기 사이의 거리를 최대로 하는 값을 반환해야함. 공유기 사이의 거리를 mid값으로 설정
• 따라서 범위도 거리가 가장 가까운 1, 가장 큰 마지막 집 - 첫 집 (정렬을 통해 보장)
• 이후, 그리디를 통해서 문제 탐색, 공유기를 설치하고, 다음 집에서의 거리가 임의로 설정한 공유기 사이 거리보다 크거나 같다면 count 증가
• count 증가 값이 최대 설치개수보다 많아지는 경우 범위 넓히. count ≥ C라는건 현재 거리에서도 충분히 C만큼 설치가 가능하다 ⇒ 거리를 증가시켜야한다.
• 결국 최댓값을 찾는 문제니 끝에 right 반환

⇒ 두 문제 모두 최대, 최소를 묻고 있다. 조건이 괴랄하고 범위를 묻는다면 이분탐색도 한번 고려