[백준] 2343 기타 레슨 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [n, m] = input[0].split(" ").map(Number);

let arr = input[1].split(" ").map(Number);
let right = arr.reduce((a, b) => a + b);
let left = 0;
let ans = Infinity;
while (left <= right) {
  let mid = parseInt((left + right) / 2);
  let cnt = 1;
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > mid) {
      cnt = Infinity;
      break;
    }
    if (sum + arr[i] <= mid) {
      sum += arr[i];
    } else {
      cnt++;
      sum = arr[i];
    }
  }
  if (cnt <= m) {
    right = mid - 1;
    ans = Math.min(ans, mid);
  } else {
    left = mid + 1;
  }
}
console.log(ans);

✔ 알고리즘 : 이분탐색

✔ 블루레이의 크기를 mid라고 했을 때 arr배열을 처음부터 돌면서 합이 mid를 넘기전까지 묶으면 된다. 만약 mid를 넘으면 cnt를 1증가시켜주고 sum을 arr의 현재 index값으로 초기화한다.

❗ 기본적인 이분탐색 문제라고 생각하고 풀었는데 틀렸습니다를 받았다 반례를 찾아보니

7 6
100 400 300 100 500 101 400

답: 500

인 경우 답이 400으로 잘못 출력되고 있는것을 확인했다. 위의 코드에서

if (arr[i] > mid) {
      cnt = Infinity;
      break;
}

이 부분이 없으면 불루레이크기를 넘더라도 무시되기 때문에 여기서 틀렸습니다 를 받은 것 같았다.

✔ 현재 mid로 불루레이크기를 잡았을 때 cnt값이 m보다 작으면 ans에 저장 후 right포인터를 이동시켜 범위를 좁게 잡는다.

✔ 난이도 : 백준 기준 실버 1