문제 바로가기

11054 가장 긴 바이토닉 부분 수열

문제 분석

알고리즘: DP

최장 증가 부분 수열(LIS) 알고리즘과 최장 감소 부분 수열(LDS) 알고리즘이 섞인 문제다. (LIS + LDS)

LIS란 주어진 N개의 배열에서 일부 원소들로 구성한 부분수열들 가운데, 각 원소를 대상으로 이전 원소보다 크다는 조건을 만족하면서 길이가 가장 긴 부분 수열을 말한다.

반대로, LDS은 부분 수열들 가운데, 각 원소를 대상으로 이전 원소보다 작다는 조건을 만족하면서 길이가 가장 긴 부분 수열을 말한다.


이 문제에서는 가장 긴 바이토닉 부분 수열을 구하라고 한다.

여기서 말하는 바이토닉 부분 수열은 한 원소를 a라고 가정할 때 a를 기준으로 이전의 원소들은 오름차순을, 이후의 원소들은 내림차순을 이루는 수열을 말한다.

LIS에 대한 자세한 풀이는 11053 가장 긴 증가하는 부분 수열 포스팅에서 풀이했다.

위 포스트에서 알 수 있듯이 LIS는 수열의 좌측에서부터 순환하지만, 반대로 LDS는 우측에서부터 순환하여 메모제이션 DP를 구성한다.


예제를 보기쉽게 표로 살펴보면 다음과 같다.

주어진 수열을 A, 부분 수열의 길이를 메모제이션할 배열을 LIS와 LDS로 각각 DP1, DP2라고 가정한다.

A = { 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 }

A1521434521
DP1 (LIS)1221334521
DP2 (LDS)1521433321

결과적으로 바이토닉 수열은 LIS 와 LDS 의 동일 인덱스끼리 합해 가장 긴 길이를 출력하면 된다.

단, 모든 부분 수열은 자기 자신을 포함하므로 기본적으로 1의 길이를 갖는다. 때문에, LIS와 LDS의 동일 인덱스끼리의 합에서 1을 뺀 값이 가장 긴 바이토닉 수열의 길이가 된다.

풀이

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

const DP1 = new Array(n).fill(1);
const DP2 = new Array(n).fill(1);

// 증가하는 수열의 DP (LIS)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (a[i] > a[j] && DP1[i] < DP1[j] + 1) {
      DP1[i] = DP1[j] + 1;
    }
  }
}

// 감소하는 수열의 DP (LDS)
for (let i = n - 1; i >= 0; i--) {
  for (let j = i + 1; j < n; j++) {
    if (a[i] > a[j] && DP2[i] < DP2[j] + 1) {
      DP2[i] = DP2[j] + 1;
    }
  }
}

let totalDP = [];
for (let i = 0; i < n; i++) {
  totalDP[i] = DP1[i] + DP2[i] - 1;
}

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