[백준] 2631 줄세우기 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const N = +input.shift();
const arr = input.map((i) => +i);
const longest = new Array(N).fill(1);

for (let i = 1; i < N; i++) {
  let cnt = 0;
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i]) cnt = Math.max(cnt, longest[j]);
  }
  longest[i] = cnt + 1;
}

console.log(N - Math.max(...longest));

✔ 알고리즘 : DP

✔ 사람을 이동시켜서 순차적으로 배치시켜야 하는 문제이다

✔ 현재 순차적으로 배치되어있는 최대 부분수열의 길이를 구하고 전체 사람 수에서 빼면 최소로 움직여서 배치할 수 있는 경우가 된다

✔ 이중 for문으로 최대 증가 부분수열의 길이를 구하여 빼면 된다.

✔ 난이도 : 백준 기준 골드 5