[boj] 2343. 기타 레슨 (node.js)

문제 요약

[boj] 2343. 기타 레슨 (node.js)

• 주어진 크기 N의 배열을 순서 그대로 M개의 그룹으로 나누고자 한다.
• 모든 그룹의 크기가 같을 때, 그룹의 최소 크기를 구하는 문제.

풀이

• 이분 탐색을 통해서 최소 크기를 탐색한다.
• 그룹의 최소 크기는 배열의 원소 중 가장 큰 원소의 크기부터 시작한다.
• 최소 크기를 알면, 해당 크기대로 나눴을 때 그룹의 개수를 구할 수 있다. 이를 조건으로 이분 탐색의 두 포인터 L, R을 이동시키며 답을 구한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

function solution() {
  const [N, M] = input().split(" ").map(Number);
  const arr = input().split(" ").map(Number);
  let max = Math.max(...arr);
  let L = max;
  let R = 1000000000;
  let result = R;
  while (L <= R) {
    let mid = Math.floor((L + R) / 2);
    if (groupCounter(mid) > M) {
      L = mid + 1;
    } else {
      result = mid;
      R = mid - 1;
    }
  }
  console.log(result);

  function groupCounter(max) {
    let cnt = 0;
    let sum = 0;
    for (let i = 0; i < N; i++) {
      if (sum + arr[i] > max) {
        sum = 0;
        cnt++;
      }
      sum += arr[i];
    }
    return ++cnt;
  }
}

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});