문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

예제 입력

9 3
1 2 3 4 5 6 7 8 9

예제 출력

17

내가 했던 풀이 방법

1. left를 강의 중 가장 긴 시간, right를 모든 강의의 총합으로 초기화한다. left는 1개씩 강의를 저장할 때라고 생각하면 최소한 가장 긴 강의가 포함되어야 하기 때문이고 right는 모든 걸 하나의 블루레이에 저장하는 것이 가장 큰 크기이기 때문이다.
2. left와 right를 이용하여 이분 탐색을 진행한다. 두 값의 중앙 값을 mid로 두고 이 mid가 블루레이 크기가 된다.
3. isPossible에 mid 값을 매개변수로 전달하고 count를 1, sum을 0으로 초기화한다. count는 블루레이의 개수가 된다. 무조건 1개는 만들어지기 때문에 1로 초기화한다. 각 강의를 순차적으로 sum에 더해준다. 만약 특정 강의를 더했을 때 size를 넘어갈 경우 다른 블루레이로 저장해야 하므로 count를 1 증가시켜주고 sum을 해당 시간으로 초기화한다. 즉 다음 블루레이의 시작이 해당 강의가 된다. size를 넘어가지 않다면 sum에 더해준다.
4. 3번을 모든 강의에 대해 검사했을 때 count가 M보다 크다면 false를 반환하고 그렇지 않다면 true를 반환한다.
5. 3~4번을 mid에 대해 검사했을 때 true가 나오면 그 size보다 더 작은 값이 가능한지 체크해야 하므로 right를 변경해주고 false가 나오면 그 값보다 더 크게 size를 설정해야 하므로 left를 변경해준다.
6. 이를 최종적으로 진행했을 때의 left 값이 블루레이 크기의 최소값이다.

코드

const fs = require('fs');
let [n, time] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let [N, M] = n.split(' ').map(Number);
time = time.split(' ').map(Number);

let left = Math.max(...time);
let right = time.reduce((a, b) => a + b, 0);

function isPossible(size) {
  let count = 1;
  let sum = 0;

  for (let i = 0; i < N; i++) {
    if (sum + time[i] > size) {
      count++;
      sum = time[i];
    } else {
      sum += time[i];
    }

    if (count > M) return false;
  }

  return true;
}

while (left <= right) {
  let mid = Math.floor((left + right) / 2);

  if (isPossible(mid)) {
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}

console.log(left);

회고

이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.라는 말을 보고 각각의 블루레이 크기가 같아야 한다고 판단했다. 그래서 더했을 때 딱 size가 되어야 하니 조건이 되게 복잡하다~ 생각했는데 힌트를 보니 저 말의 뜻은 크기가 13, 15, 17이라면 블루레이 하나의 크기를 17로 잡겠다였다. 즉, 최댓값이 size가 되면 된다~였던것이다. 흠... 내 어휘력 문제.......인가? 튼 그거 아니였다면 딱 이분탐색이 생각날법한 문제였다.