[白俊]配置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);
✔最長減少部分数列の個数を作るために、取り除く必要がある兵士の数の問題
✔reverse関数で数列を反転し、DPで最長増分部分数列の長さを求める
✔数列の要素の個数の中で最も長い部分の数列の長さの値を減らしてansになります
✔難易度:白駿基準シルバー2
Reference
この問題について([白俊]配置18353兵士-javascript), 我々は、より多くの情報をここで見つけました https://velog.io/@ywc8851/백준-18353-병사-배치하기-javascriptテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol