[백준][[이분탐색] 2343 기타레슨 NodeJs 구현

목차

 

문제

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

 

 

문제 구현 방향

범위를 정확하게 하고 초기화를 정확하게 하지 않으면 반례에 직면한다. 블루레이 하나가 최대 크기를 초과할 수 있으므로 low는 배열에서 가장 큰 값으로 해준다..

 

 

 

코드 구현

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

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

let high = arr.reduce((acc, el) => acc + el, 0);
let low = Math.max(...arr);
let ans = 0;

while (low <= high) {
  let mid = Math.floor((low + high) / 2);
  //console.log("mid: ", low, high, mid);
  let total = 0;
  let cnt = 0;
  for (let i = 0; i < arr.length; i++) {
    if (total + arr[i] > mid) {
      total = 0;
      cnt++;
    }
    total += arr[i];
  }
  if (total) cnt++;
  if (cnt <= M) {
    ans = mid;
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
console.log(ans);