문제 바로가기

11053 가장 긴 증가하는 부분 수열

문제 분석

알고리즘: DP

해당 문제는 주어진 수열에서 오름차순으로 증가하는 원소들만으로 가장 긴 길이를 찾는 문제로,

주어진 수열들을 순회하면서 각 수열이 가질 수 있는, 오름차순을 이루는 수열의 길이를 구하면 된다.

이는 이중 반복문으로 구현할 수 있을 것이다.

예제로, 수열 {10, 20, 10, 30, 20, 50} 이 주어질 때, 이를 배열 변수 A 라고 하고, 오름차순을 이루는 수열의 길이를 메모제이션할 배열 변수를 DP 라고 가정해보자.

먼저, 모든 부분수열이 자기 자신을 반드시 포함하기 때문에 기본적으로 하나의 수열을 기본 갖는다.

  • A[0] 이전 값이 없으므로 기본적으로 부분 수열 10을 갖기 때문에 길이는 1, DP[0]=1
  • A[1] 대상으로 하는 부분 수열이 20 이므로 길이는 2, DP[1]=2
  • A[2] 대상으로 하는 부분 수열이 10이므로 길이는 1, DP[2]=1
  • A[3] 대상으로 하는 부분 수열이 30 이므로 길이는 3, DP[3]=3
  • A[4] 대상으로 하는 부분 수열이 20 이므로 길이는 2, DP[4]=2
  • A[5] 대상으로 하는 부분 수열이 50 이므로 길이는 4,DP[4]=4

표로 보면 다음과 같다.

A102010302050
DP121324

풀이

dp 배열을 1로 초기화하는 이유는 위에서 말했듯이 모든 부분수열이 자기 자신을 반드시 포함하기 때문에 기본적으로 하나의 수열을 기본으로 갖게되기 때문이다.

const [N, input] = require('fs').readFileSync('dev/stdin').toString().split('\n');
const n = parseInt(N);
const a = input.split(' ').map(Number);

const dp = new Array(n).fill(1);

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

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