백준 13397 구간 나누기2

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

문제

1차원 배열을 M개로 나눈 다음에, 가진 구간 점수의 최댓값의 최솟값을 푸는 문제이다. 맨 처음에 브루트포스로 풀어야 하는 문제인줄 알았다. 하지만 딱 봐도 5000개까지 나오는 배열에 구간을 나눠서 완탐하게 되면 딱봐도 시간초과 할게 뻔해보였다. 아무리 생각해도 모르겠어서 해설을 봤는데 이분탐색으로 푸는 문제였다.

여기서 중요한 점은 구간을 계속 나누면서도, M개의 구간을 넘지 않도록 해야 하고, 최댓값중에 최솟값을 구해야 한다는 사실이다. 이를 반대로 생각하면 이 최댓값중에 최솟값이 될 수 있는 값을 최대로 잡아놓고 점점 범위를 좁혀가면서 범위 안의 구간으로 나누어질 수 있는 경우를 찾으면 된다.

구간이 나누어질 수 있는 경우를 찾기 위해서는, right를 처음에는 가장 최대의 값으로 잡는다. 그리고 left와right의 값 가운데인 mid의 값을 가질 수 있는 최댓값-최솟값이 가질 수 있는 최댓값으로 잡는다. 이 이상으로 넘어가면 애초에 우리가 현재 탐색하면서 찾는 값이 지금 찾는 범위 밖까지 나갔다는 의미이기 때문에 이 안쪽 범위의 구간 최댓값만 구한다.

만약 반대로 이 범위 안에 들어갔으면 이는 곧 구간 하나가 나뉘어질 수 있다는 의미이다. 따라서 나누어질 수 있는 구간을 하나 더 추가해준다. 마지막에 구간을 다 나누어 봤을 때, m 이하의 구간이 나오게 되면 이 경우에 최댓값의 최솟값(m)을 업데이트 시켜준다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [n, m] = inputs[0].split(" ").map(Number);
const arr = inputs[1].split(" ").map(Number);
 
let left = 0;
let right = Math.max(...arr);
let result = Infinity;
 
while (left < right) {
  let mid = Math.floor((left + right) / 2);
  if (possible(mid)) {
    if (result > mid) result = mid;
    right = mid;
  } else left = mid + 1;
}
 
function possible(mid) {
  let max = -Infinity;
  let min = Infinity;
  let cnt = 1;
  for (let i = 0; i < n; i++) {
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
    if (max - min > mid) {
      cnt++;
      max = arr[i];
      min = arr[i];
    }
  }
  return cnt <= m;
}
console.log(result);
 

이분탐색은 단순하게 탐색하는 정도의 문제만 풀어봤는데, 조금 더 꼬아서 내니 생각보다 이걸 어떻게 풀지 막막해지면서 이분탐색으로 풀어야겠다는 생각조차 못했던 것 같다..;; 이분탐색을 더 공부해서 이를 조금 더 보완해야 할 것 같다.