99클럽 코테 스터디 11일차 TIL - 과자 나눠주기 (이진탐색)

문제: https://www.acmicpc.net/problem/16401

접근 방식

• 가능한 과자 길이의 범위는 1 ~ 가장 긴 과자 길이
• 길이 x로 자를 수 있는 조각 수가 M 이상인지 판단(count)
• 이분 탐색으로 범위를 좁혀가며 가능한 최대 길이를 찾을 수 있음

구현

const fs = require("fs")
const [[m, n], arr] = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(s => s.split(" ").map(Number))

let left = 1
let right = Math.max(...arr)
let maxLength = 0;

while (left <= right) {
  const mid = Math.floor((left + right) / 2)
  const count = arr.reduce((acc, cur) => acc + Math.floor(cur / mid), 0)

  if (count >= m) {
    maxLength = mid
    left = mid + 1
  } else {
    right = mid - 1
  }
}

console.log(maxLength)