[백준16401_자바스크립트(javascript)] - 과자 나눠주기

🔴 문제

과자 나눠주기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[m, n], sticks] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

let left = 1;
let right = Math.max(...sticks);
let answer = 0;
while (left <= right) {
  const mid = Math.floor((left + right) / 2);
  let stickCnt = 0;

  for (const stick of sticks) {
    stickCnt += Math.floor(stick / mid);
  }

  if (stickCnt < m) right = mid - 1;
  else {
    left = mid + 1;
    answer = mid;
  }
}

console.log(answer);

🟢 풀이

⏰ 소요한 시간 : -

이분탐색의 응용인 매개변수 탐색(파라메트릭 서치) 유형이다.
나눠줄 수 있는 과자의 길이를 이분탐색을 사용해 빠르게 모두 탐색하면된다.
과자의 최소 길이를 1, 최대 길이를 과자의 길이중 최대값으로 잡고 이분탐색을 수행한다.
모든 과자들을 mid 값으로 나눈뒤 나온 과자 조각의개수와 아이들의 인원수 m과 비교해주면 되는데, 이 때 최적의 값을 찾아줘야 하므로 조건을 만족했을 경우 정답을 업데이트 시킨 뒤 다음 탐색을 이어 한다.

🔵 Ref