출처

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

문제풀이

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
var [N, H] = input.shift().split(" ").map(Number);
var Trees = input.shift().split(" ").map(Number);
var MaxH = Math.max(...Trees);

function binarySearch(H, Trees, min, max) {
  let mid = 0;
  let BestH = 0;
  
  while (min <= max) {
    let SumWood = 0;
    mid = Math.floor((min + max) / 2);
    Trees.forEach((a) => {
      let rest = a - mid;
      if (rest > 0) SumWood += rest;
    });
    if (SumWood >= H) {
      if (mid > BestH) BestH = mid;
      min = mid + 1;
    } 
    else {
      max = mid - 1;
    }
  }
  return BestH;
}

const answer = binarySearch(H, Trees, 0, MaxH);
console.log(answer);

환경에 관심이 많은 상근이를 위해 가장 효율적으로 나무를 자르는 높이를 구하는 문제.

1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000

주어지는 입력값이 매우 큰 수이기때문에 모든 수를 순회하면서 풀면 시간초과가 난다.
이분탐색을 이용하여 문제를 해결해 보았다.

자르는 높이는 주어진 나무들 중 가장 큰 나무보다 클 수 없기 때문에 범위를 0 - Math.max(...Trees)로 잡았다.

그 후 초기 중앙값을 잡고 중앙값보다 큰 나무
나무 - 중앙값 = 양수를 합산해 주었다.
합산한 나무의 값이 필요한나무보다 많거나 같고, 현재 최적의 높이보다 중앙값이 더 크다면 그 값이 최적의 높이이다. 그 후 찾고자하는 값은 중앙값의 오른쪽에 위치하므로 최소값을 재조정해준다.
합산한 나무의 값이 필요한나무보다 적으면, 찾고자하는값은 중앙값의 왼쪽에 위치하므로 최대값을 재조정해준다.

이분탐색을 이해한다면 풀수있는 문제였다.