[백준 2565번] DP(다이나믹 프로그래밍) - 전깃줄

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

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

input=input.split('\n')
let N=+input.shift();

input=input.map((el)=>el.split(' ').map((el2)=>+el2));

const solution=(N, input)=>{
    let dp=new Array(N).fill(1);
    // 왼쪽 줄을 기준으로 오름차순 정렬.
    input.sort((a,b)=>a[0]-b[0]);

    for (let i=1;i<N;i++){
        let current=input[i][1];
        let count=0;
        for (let j=0;j<i;j++){
            let before=input[j][1];
            if (current>before) {
                count=Math.max(count, dp[j])
            }
        }
        dp[i]=count+1;
    }
    console.log(N-Math.max(...dp))

}
solution(N, input)

🧵 참고한 정답지 🧵

https://junghyeonsu.tistory.com/209

💡💡 기억해야 할 점 💡💡

아무리 봐도 교차하는 경우(A, B 사이에 얼마나 많은 선이 있는지)를 찾아서 dp화함으로써 문제를 풀어야 할 것 같았는데...
1. 가장 긴 오름차순 부분 수열의 길이를 구하는 것과 같다고 한다.