[JavaScript] 백준 2565 전깃줄 (JS)

전깃줄

📚 문제 설명

A전봇대와 B전봇대 사이에 전깃줄이 있다.
전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다.

전깃줄이 서로 교차하지 않도록 하고 싶을 때 최소 몇개의 전깃줄을 제거하면 되는가?

👨🏻‍💻 풀이 과정

우선 입력으로 전깃줄의 시작 위치가 랜덤하게 주어지기 때문에 sort()를 이용해 시작위치 기준 오름차순으로 바꿔주어야 한다.
그럼 여기서 교차 없이 만들기 위해서는 이 수열이 오름차순이 되도록 만들면 된다. (시작 기준 오름차순 정렬을 했기 때문)

따라서 백준 가장 긴 증가하는 부분 수열 문제와 똑같다고 생각하면 된다.

예를 들어 오름차순 정렬 후 끝부분이 8, 2, 9, 1, 4, 6, 7, 10라고 할 때,
1, 4, 6, 7, 10 이 가장 긴 증가하는 부분 수열이고 길이는 5이다.
그럼 반대로 5개를 제외하고 나머지 전깃줄을 제거하면 그 때가 최솟값이다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const LINE = parseInt(input.shift())
    const lines = input.map(v => v.split(' ').map(Number));
    lines.sort((a, b) => a[0] - b[0]);

    let dp = new Array(LINE).fill(1);

	// 가증 긴 증가하는 부분 수열 계산.
    for (let i = 1; i < dp.length; i++) {
        for (let j = 0; j < i; j++) {
            if (lines[i][1] > lines[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
	// 전체 전깃줄에서 가장 긴 부분수열의 길이를 빼준다.
    console.log(LINE - Math.max(...dp));

🧐 후기

문제를 처음 접근할 때, 잘못 접근해서 상당히 고민했던 문제였다.