백준 JS 7570번 줄세우기 LCS

 

7570번: 줄 세우기

꼭 알아야 하는 개념인 LCS를 활용한 문제입니다.

LCS는 2차원 DP로 푸는 경우가 많아서 이 문제를 처음 봤을 때 고민을 많이 했습니다.

복습 차원에서 글을 적습니다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const N = +input.shift()
const dp = Array(N+1).fill(0)

let max = 0;
for(let number of input[0].split(" ").map(Number)){
  dp[number] = Math.max(1,dp[number-1]+1)
  if(dp[number] > max){
    max = dp[number]
  }
}
console.log(N-max)