프로그래밍/알고리즘 풀이
[node.js] 가장 긴 증가하는 부분 수열 ( 백준 11053번 )
카카수(kakasoo)
2021. 3. 30. 17:59
반응형
나는 이걸 틀려서, 결국 다른 사람의 코드를 참고했었다. 유명한 알고리즘이라 별도의 이름도 있다고 한다.
LIS 라고 하는데, 말 그대로 Longest Increase Sequence? 뭐 그런 이름이었던 거 같다.
나는 이걸 짜기 위해서 n이 증가함에 따라 이전에 가능했던 수열에 새 값을 붙인 경우, 붙이지 않은 경우를 탐색했는데,
메모리 초과가 심각해서 풀 수가 없었다.
DP는 DP 방법 말고는 답이 없는 듯 하다.
다음 문제가 가장 긴 감소하는 부분 수열인데,코드를 전혀 보지 않고 풀어보도록 하자.
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let count = 0;
rl.on("line", (line) => {
if (!count) {
count = Number(line);
} else {
main(line);
rl.close();
}
}).on("close", () => {
process.exit();
});
/**
*
* @param {string} line
*/
const main = (line) => {
const numbers = ("0 " + line).split(" ").map(Number);
const DP = new Array(count + 1).fill(1);
for (let i = 2; i < DP.length; i++) {
let temp = 0;
for (let j = 1; j < i; j++) {
if (numbers[j] < numbers[i]) {
if (temp < DP[j] + 1) {
temp = DP[j] + 1;
}
}
if (temp != 0) {
DP[i] = temp;
}
}
}
console.log(Math.max(...DP));
};
반응형