[백준] 18353 병사 배치하기 - javascript

📌 문제

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

📌 풀이

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

let n = Number(input[0]);
let nums = new Array(n);
let dp = new Array(n + 1).fill(1);
nums = input[1].split(" ").map(Number);
nums.reverse();
// 최장 증가 부분 수열
for (let i = 1; i < n; i++) {
  for (let j = 0; j <= i; j++) {
    if (nums[i] > nums[j]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}
let ans = 0;
for (let i = 0; i <= n; i++) {
  ans = Math.max(ans, dp[i]);
}
console.log(n - ans);

✔ 알고리즘 : DP

✔ 가장 긴 감소하는 부분수열의 개수를 만들기 위해 제거해야하는 병사의 수를 구하는 문제이다

✔ reverse함수를 통해 수열을 뒤집고 가장 긴 증가하는 부분수열의 길이를 DP를 통해 구한다

✔ 수열의 원소개수에서 가장 긴 증가하는 부분수열의 길이를 뺀 값이 ans가 된다

✔ 난이도 : 백준 기준 실버 2