나무 자르기

• https://www.acmicpc.net/problem/2805

오늘의 학습 키워드

이진탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
• 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다
• 각 단계마다 탐색 범위가 반으로 감소하므로, 로그(log) 복잡도를 가진다

대표적인 사례

• 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

문제 해결 방법

• 이진탐색을 활용해 설정 가능한 높이의 최댓값을 구한다
  • r(right)값은 Math.max(...trees)로 설정한다
  • remains가 구해야 하는 값(M)보다 작다면 r = mid - 1, 크거나 같다면 l = mid + 1; result = mid;의 과정을 거쳐 최선의 결과를 찾는다

코드

const fs = require("fs");
const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
const [[N, M], trees] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((line) => line.split(" ").map(Number));

let l = 1;
let r = Math.max(...trees);
let result = 0;

while (l <= r) {
  let mid = parseInt((l + r) / 2);
  const remains = trees.reduce((acc, cur) => acc + Math.max(cur - mid, 0), 0);

  if (remains < M) r = mid - 1;
  else {
    l = mid + 1;
    result = mid;
  }
}

console.log(result);