[JS] 백준 2565번 전깃줄

---

문제 링크

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

풀이 전략

문제의 요지는
서로 교차하지 않기 위해 없애야하는 전깃줄의 최소 개수를 구하는 것이다.
그리디 풀이 방식으로 가장 많이 교차하고 있는 전깃줄을 없애가며 풀 수 있지만dp로 풀기 위해서는 이를 반대로 생각할줄 알아야했다.
전깃줄이 꼬이지 않게 하려면 오른쪽에 있는 전깃줄들의 번호가 오름차순이어야한다.
다시말해, 우리는 우리가 없애야하는 전깃줄을 최소로 하기 위해서, 전체 전봇대중 가장 긴 증가하는 부분수열(LIS)을 찾으면 된다.
이게 왜 가능하냐면, 만약 전깃줄이 꼬여있을 때 오른쪽 전깃줄의 전기선은 오름차순으로 가다가 중간중간 낮아지는 부분들이 있을 것이다. 이 부분의 전깃줄만 제거한다면, 우리가 원하는 최소의 갯수로 꼬인 전깃줄을 풀 수 있는 답이 된다. 

코드 

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];
rl.on("line", function (line) {
    input.push(line.split(" ").map(Number));
}).on("close", function () {
    solution(input);
    process.exit();
});

const solution = (arr) => {
    const N = arr.shift()[0];
    const dp = Array.from({length : N}, () => 1);
    
    arr.sort((a, b) => a[0] - b[0]);

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

// 10
// 1 6
// 2 8
// 3 2
// 4 9
// 5 5
// 6 10
// 7 4
// 8 1
// 9 7
// 10 3

 

회고

오랜만에 알고리즘 문제를 풀려니 잘 안된다. 이제 다시 차근차근 풀어봐야겠다. 

 

참고 링크

- https://yabmoons.tistory.com/572

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)