백준11722 - 가장 긴 감소하는 부분 수열(DP) node.js

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

해당 문제는 다이나믹 프로그래밍으로 문제해결이 가능하다.

 

풀이 과정은 다음과 같다.

먼저 수열의 '길이'를 출력하는 것이므로, DP 테이블의 기본값은 1로 설정한다. (자기 자신만 포함하는 경우)

여기서 두번째 반복문의 범위는 0 <= j < i 로 설정하는데, 현재 요소 arr[i]를 기준으로 이전 요소들을 비교하며 가장 긴 감소하는 부분 수열의 길이를 갱신하기 위함이다. (따라서 현재 요소 이전의 모든 요소들을 순회)

이후, 감소하는 부분 수열이므로 arr[j] > arr[i] 조건을 만족하며,

이전 요소를 마지막으로 하는 부분 수열의 길이에서 현재 요소를 추가할 경우의 길이(dp[j] + 1)가,

현재 요소를 마지막으로 하는 부분 수열의 길이(dp[i])보다 큰 경우 dp[i] = dp[j] +1 로 값을 수정해 나아가며 dp 테이블을 완성한다.

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

function solution(data) {
  const n = +data[0];
  const arr = data[1].split(" ").map(Number);
  const dp = Array.from({ length: n }, () => 1);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }

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

solution(input);