백준, 2343 기타레슨 자바스크립트

백준, 2343 기타레슨 자바스크립트

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

👨‍💻 문제 풀이

• 사실 이렇게 로직정리했을때 대충 60% 까지 올라가길래 금방 끝날줄 알았는데 함정이 많았다..!
• 고생했던 포인트: 이 문제는 M을 딱 맞추지 않아도 된다.(그런 조건없음. CNT보다 같거나 작기만 하면 되고, CNT보다 낮을때 최댓값을 가질 수도 있음)
• 고생했던 포인트2: 이분탐색의 left는 항상 최솟값이 아니다.
  - 이 문제는 나누지 못하는 길이를 채워야 한다.
  • 무조건 가장 큰 길이를 가지는 블루레이가 최솟값이 되어야 한다.
  • 그 길이를 나누어서 저장할 수 없기 때문이다.

💻 제출한 코드

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const [N, M] = input.shift().split(' ').map(Number);
const classes = input[0].split(' ').map(Number);

let left = Math.max(...classes);
// 첫번째 틀린 포인트 left = 1
// https://www.acmicpc.net/board/view/49644

let right = classes.reduce((acc, cur) => acc + cur);

let answer = Number.MAX_SAFE_INTEGER;
while (left <= right) {
  let cnt = 1;
  let mid = Math.floor((left + right) / 2);
  let tmp = 0;
  for (let i = 0; i < classes.length; i++) {
    if (tmp + classes[i] <= mid) {
      tmp += classes[i];
    } else {
      tmp = 0 + classes[i];
      cnt++;
      if (cnt > M) break;
    }
  }

  // if (cnt === M) {
  //   if (answer >= mid) answer = mid;
  //   right = mid - 1;
  // }
  // 두번째 틀린 포인트

  if (cnt > M) {
    left = mid + 1;
  }

  if (cnt <= M) {
    if (answer >= mid) answer = mid;
    right = mid - 1;
  }
}

console.log(answer);

반례 모음

https://bingorithm.tistory.com/10

이번 문제를 풀면서,

• 문제를 정확히 이해하자.
• 어떻게 보면 약간 말장난도 조심해야 한다.
• 이분탐색의 최솟값, left가 항상 제일 작은 값이 아니다.