🎲 백준 2565번 전깃줄

백준 2565번

💊 가장 긴 오름차순 부분수열 길이를 구하는 문제인데 아이디어를 떠올리지 못했다..ㅠ
🎨 참고 코드

코드

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

const N = +input.shift();
input = input
  .map((item) => item.split(" ").map(Number))
  .sort((a, b) => a[0] - b[0]);

let dp = new Array(N).fill(1);
for (let i = 1; i < N; i++) {
  let max = dp[i];
  for (let j = 0; j < i; j++) {
    if (input[j][1] < input[i][1]) {
      max = Math.max(max, dp[j] + 1);
    }
  }
  dp[i] = max;
}

console.log(N - Math.max(...dp));