[백준/G4] 2631 줄세우기

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

시간복잡도

O(N**2)

풀이

LIS알고리즘에 대한 이해가 필요한 문제였다.
dp를 활용함으로서 LIS의 최장길이를 구하고 (+ dp보단 이분탐색의 방법이 더 빠르다고는 함)
전체길이에서 해당길이를 빼주면 옮겨져야하는 아이의 최소수를 구할 수 있다.

최종코드

// 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./2631.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input[0]);
const numbers = input.slice(1).map(Number);

// LIS (최장 증가 부분 수열) 알고리즘을 활용, dp에 LIS의 최대 길이를 담자
const dp = new Array(N).fill(1);

// 각 인덱스에 대해 이전 인덱스의 값들과 비교하며,
// numbers[i]가 numbers[j]보다 큰 경우 dp[i]를 업데이트
// dp[i]는 numbers[i]까지의 LIS 길이
for (let i = 1; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (numbers[i] > numbers[j]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

const LISLength = Math.max(...dp);

// 전체 길이에서 LIS의 최장 길이를 빼면 최소로 옮겨져야하는 수를 구할 수 있음
let ans = N - LISLength;

console.log(ans);

9624kb 152ms