BOJ : 2565 전깃줄(JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log
let lst = []

for (let i = 1 ; i <= input[0] ; i++){
    let numbers = input[i].split(" ").map(Number)
    lst.push(numbers)
}

lst.sort((a,b) => a[0] - b[0])

let dp = []

for(let i = 0 ; i < Number(input[0]) ; i++){
    dp[i] = 1
}

for(let i = 1 ; i < Number(input[0]) ; i++){
    for(let j = 0; j < i ; j++){
        if(lst[j][1] < lst[i][1]){
            dp[i] = Math.max(dp[i],dp[j]+1)
        }
    }
}

c(Number(input[0]) - Math.max(...dp))

 

풀이

전봇대 a를 기준으로 오름차순으로 정렬해 준 후 대각선이 겹친다는 것은 a -> b로 가는 선이 두개가 존재 할때 x 자로 된다는 것인데 전봇대 b도 가장 긴 오름차순 즉 가장 긴 증가하는 수열을 구하면된다.

 

문제

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

2565번: 전깃줄