백준 2565 전깃줄

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

문제

교차하지 않도록 전깃줄을 끊어야 하는데, 최대한 적게 끊는 개수를 구하는 문제이다. 이건 끊어야 할 전깃줄을 구하는 것보다, 역으로 생각해보는 창의력이 필요하다. 백준 푸는 사람들은 다 씽크빅 다녔나보다

아무튼 끊어야 할 전깃줄은 곧 교차하고 있는 두 개의 전깃줄 중 하나를 의미한다. 이러한 전깃줄을 최소한으로 끊기 위해서는 거꾸로 최대한 많이 겹치지 않은 상태를 찾은 후, 전체 길이에서 최대한 많이 겹치지 않은 상태를 빼게 되면 끊어야 하는 전깃줄의 최소 개수를 구할 수 있다. 이를 구하기 위해서는 왼쪽을 기준으로 오름 곧 LIS(최장 증가 부분 수열) 구하기 알고리즘과 같다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...w] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const dp = new Array(100).fill(1);
const wires = w.map((w) => w.split(" ").map(Number));
wires.sort((a, b) => a[0] - b[0]);
 
for (let i = 1; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (wires[i][1] > wires[j][1]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}
console.log(n - Math.max(...dp));

이는 애초에 각 이어진 전깃줄이 100개 이하였기 때문에 가능하지만, 기본적으로 LIS 알고리즘은 O(N^2)의 시간 복잡도를 가지고 있기 때문에 케이스가 더 많을 경우에는 효율적이지 못한 알고리즘일 수 있다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [n, ...w] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const dp = new Array(100).fill(1);
const wires = w.map((w) => w.split(" ").map(Number));
wires.sort((a, b) => a[0] - b[0]);
 
const lis = [];
for (const [, b] of wires) {
  let left = 0,
    right = lis.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (lis[mid] >= b) right = mid;
    else left = mid + 1;
  }
  if (left < lis.length) lis[left] = b;
  else lis.push(b);
}
console.log(n - lis.length);

이분 탐색을 활용하여 O(n log n)까지 개선할 수 있었다.