[JavaScript/DP] 백준 골드 5 : 2565 - 전깃줄

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

 

---

📌 작성한 코드 

// 2565
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const list = input.map((str) => str.split(" ").map(Number)).sort((a, b) => a[0] - b[0]);
const lines = list.map(([_, val]) => val);

// 가장 긴 증가하는 부분 수열의 길이 구하기
// dp[i] = i를 마지막 값으로 가지는 증가 수열의 길이

const dp = Array(N).fill(0);

for (let i = 0; i < N; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
        if (lines[i] > lines[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

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

 

📌 설명 

1. 전깃줄을 입력받은 후에 전깃줄의 시작점(왼쪽)을 기준으로 오름차순 정렬한다.

2. 전깃줄의 끝점을 기준으로 보았을 때 가장 긴 증가하는 수열의 길이를 구하면 교차하지 않고 남아있을 수 있는 최대 전깃줄의 개수를 구할 수 있다.

3. 남아있을 수 있는 전깃줄의 개수를 구했으니 총 전깃줄의 개수에서 해당 개수를 빼주면 원하는 제거해야 하는 최소 전깃줄의 개수를 구할 수 있다.

✅ 성공