백준2805 - 나무 자르기 (이분탐색) node.js

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

해당 문제는 나무의 갯수 N, 필요한 나무의 길이 M 그리고 N개의 나무 각각의 길이가 주어질 때, 필요한 나무의 길이 M을 만들기 위한 최대의 절단기 길이를 구하는 문제다.

처음에는 문제의 장르가 이분탐색으로 설정되어 있음에도 어떻게 접근해야 할지 난해했다.

하지만 머리를 굴리다, 특정 길이로 잘랐을 때 얻을 수 있는 나무의 길이를 계산한 뒤 이를 활용하여 이분탐색의 범위를 조절하는 방식으로 해결했다.

 

문제 풀이 방식

이분탐색에서 활용하기 위한 범위를 설정한다. 최소 범위는 0, 최대 범위는 주어진 나무의 길이 중 가장 큰 것으로 초기화한다. (최대 범위가 나무의 길이 중 가장 큰 값일 경우 가져갈 수 있는 나무의 양도 최대가 되기 때문)

이후 while문에서는 중간값을 구한 뒤, 해당 중간값으로 나무를 잘랐을 경우 가져갈 수 있는 총 나무 길이를 구한다.

그리고 이 나무 길이를 trees라고 할 때, 해당 값이 문제에서 필요로 하는 나무의 길이보다 크거나 같을 경우 최소 범위를, 작을 경우는 최대 범위를 더 좁게 수정한다.

같을 경우 답을 리턴하는 것이 아니라, 크거나 같을 경우에도 범위를 좁히는 이유는 다양할 수 있겠지만 이 문제의 경우 최적의 값을 찾는 것이 아닌 조건을 만족하는 값 중에서 가장 큰 값을 찾는 것이 목표기 때문에,

start의 범위를 더 큰 값으로 수정하여 해당 탐색을 모두 진행한 뒤 end를 결괏값으로 출력한다. (최댓값을 찾고자 하는 것이므로, start의 범위를 최대한 높이는 방식으로 모든 탐색을 진행하는 것이라 이해하면 좋다.)

이때 end는 모든 탐색이 완료되었을 때 조건을 만족하는 최댓값이 담겨 있는 변수기도 하며, while문 탈출조건이 (start > end)이므로 start - 1 과 end 값은 같은 값을 지닌다. 

 

전체 소스 코드

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

function solution(data) {
  const [[_, m], arr] = data.map((el) => el.split(" ").map(Number));
  let start = 0;
  let end = Math.max(...arr);

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const trees = arr.reduce((acc, cur) => {
      return acc + (cur - mid > 0 ? cur - mid : 0);
    }, 0);

    if (trees >= m) start = mid + 1;
    else end = mid - 1;
  }
  console.log(end);
}

solution(input);