백준 JS 2565번 전깃줄 DP

첫 번째 풀이

1. 가장 많이 꼬인 전깃줄을 차례로 제거하면서 꼬인 줄이 없을 때 까지 반복한다.

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

let countArr = Array.from({length:N},(v,i)=>[i,[],0])
for(let i=0; i<data.length; i++){
  for(let j=0; j<data.length; j++){
    if( i !== j){
      const [str1, end1] = data[i]
      const [str2, end2] = data[j]
      if((str1 > str2 && end1 < end2 )||(str1 < str2 && end1 > end2)){
        countArr[i][1].push(j)
        countArr[i][2]++
      }
    }
  }
}

let answer = 0;
while(true){
  const deleteIndex = countArr.sort((a,b) => a[2] - b[2]).pop()
  if(deleteIndex[2] === 0){
    break;
  }
  answer++
  for(let i=0; i<countArr.length; i++){
    const current = countArr[i];
    if(current[1].indexOf(deleteIndex[0])!== -1){
      current[2]--
    }
  }
}
console.log(answer)

많이 꼬인 순서대로 전깃줄을 제거하면 문제가 풀리지 않는다.

반례

5
1 3
3 1
4 6
6 4
2 5

answer: 2

(3 1), (6 4)을 잘라야 함.

---

두 번째 풀이

1. DP를 만들어서 생각한다.
2. 줄의 시작 지점을 기준으로 정렬을 한 다음, 시작 지점이 작은 숫자대로 순회.
3. DP에는 하나의 줄을 기준(i )으로 그 줄의 시작지점 보다 더 작은 숫자를 시작 지점으로 가진 줄을 순회하고(j), 그 줄의 도착 지점이 기준이 되는 줄의 도착 지점을 넘지 않는다면 꼬이지 않는 것 이기 때문에 DP에 값을 넣을 수 있다(dp[j]+1).
4. 순회를 여러번 하기 때문에 최댓값을 넣기 위해서 Math.max(dp[i], dp[j]+1) 값을 적어준다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim()
  .split("\\n");
const N = +input.shift();
const data = input.map((v) => v.split(" ").map(Number)).sort((a,b)=>a[0]-b[0]);
const dp = Array.from({length:N}, ()=>1)

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