[백준][이분 탐색] 2792 보석 상자 NodeJs구현

목차

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

문제

 

문제 구현 방향

1억의 범위이기 때문에 O(N)이 안될 것이라는 것을 잡고 가야 한다. 따라서 이분 탐색을 통해 O(logN)을 

만들어 주어야 한다.

 

 

문제 아이디어

아이들의 수에 보석수를 나누어 주었을 때 몫만큼 더해주고 나머지가 있다면 1만 늘려주면 된다.

그러면 보석에 대해 나누어준 아이들의 수를 구할 수 있다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M] = input[0].trim().split(" ").map(Number);

let arr = [];
for (let i = 1; i < input.length; i++) {
  arr.push(Number(input[i]));
}

let str = 1;
let end = Math.max(...arr);
let ans;
while (str <= end) {
  let cnt = 0;
  let mid = Math.floor((str + end) / 2);
  for (let i = 0; i < arr.length; i++) {
    cnt += Math.floor(arr[i] / mid);
    if (arr[i] % mid !== 0) cnt++;
  }
  if ((cnt <= N)) {
    end = mid - 1;
    ans = mid;
  } else {
    str = mid + 1;
  }
}
console.log(ans);