[백준11722_자바스크립트(javascript)] - 가장 긴 감소하는 부분 수열

🔴 문제

가장 긴 감소하는 부분 수열

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [head, tail] = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(head);
const a = tail.split(' ').map(Number);
const dp = tail.split(' ').map((it) => 1);

for (let i = 1; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (a[i] < a[j]) {
      dp[i] = Math.max(dp[j] + 1, dp[i]);
    }
  }
}

console.log(Math.max(...dp));

🟢 풀이

⏰ 소요한 시간 : 15분

가장 긴 증가하는 부분 수열과 동일한 원리로 풀면된다.
dp 배열은 각 위치에서의 가장 긴 감소하는 부분 수열의 길이를 저장한다.
즉 dp 배열의 i번째 요소는 지금까지 가장 긴 감소하는 부분 수열의 길이가 몇인지 저장하는 것이다.
0번째 요소인 10은 가장 긴 감소하는 부분수열의 길이가 1이니까 i는 1번째 인덱스부터 순회해주면 된다.
이후의 요소들은 0부터 i 직전까지 순회하면서 최소값을 찾아주는데, 만약 감소하는 양상을 띌 때만(a[i] < a[j] 인 경우에만) dp 배열을 업데이트 해주면 된다.

🔵 Ref

[백준11053_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열