백준 2565: 전깃줄 - javascript(dp)

문제 출처 

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

 

정답 풀이 

문제의 핵심은, 

최장 증가 부분 수열을 이용하여 교차하지 않는 전깃줄의 최대 개수를 구하고, 

나머지 전깃줄을 제거하는 방식 이다 ! 

 

- 두 전깃줄이 교차하는 조건은, 한쪽 끝이 연결된 A 전봇대에서의 순서와 다른 쪽 끝이 연결된 B 전봇대에서의 순서가 교차할 때이다. 

- 전깃줄이 교차하지 않게 하기 위해서는 B 전봇대에 연결된 번호가 증가하는 부분 수열이어야 한다.  

 

A 전봇대에서의 순서를 기준으로 정렬한 후, B 전봇대에서의 최장 증가 부분 수열을 구하는 문제다. 

최장 증가 부분 수열의 길이를 구하면, 그만큼의 전깃줄은 제거할 필요가 없으므로 전체 전깃줄에서 이 수를 뺀 값이 답이 된다. 

 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift()); 
const arr = input.map(el => el.split(' ').map(v => +v))

function solution(n, arr){
    arr.sort((a,b) => a[0] - b[0]); 
    let dp = Array.from({length: n}, () => 1)
    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)
            }
        }
    }
    let max = Math.max(...dp)
    return n-max
}

console.log(solution(n, arr))