[Node.js] 11054_가장 긴 바이토닉 부분 수열

문제

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

풀이

이번 문제는 DP를 이용한 LIS 알고리즘 문제이다.

처음 이 문제를 보고 바이토닉 수열이라는 개념에 대해 이해하기 쉽지 않았다...

 

각 자리수에서 좌/우로 증가, 감소하는 수들의 개수의 최대값을 구하는 문제이다.

 

좌에서 우로 이동하며 증가하는 수의 연속과 우에서 좌로 이동하며 증가하는 수의 연속을 측정한다. 이 두가지 과정의 결과를 이용해 바이토닉 수열의 최대값을 구할 수 있다.

 

각 과정에서 나온 증가되는 수의 개수는 dp1, dp2에 담기며, 두 배열에서 인덱스가 같은 값들을 더해주고, 이 중 최대 값을 제출한다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n')

const N = input.shift();
let arr = input.shift().split(' ').map(Number);
let dp1 = new Array(+N).fill(1);
let dp2 = new Array(+N).fill(1);

for (let i = 0; i < N; i++){
  const curN = arr[i];
  for (let j = i - 1; j >= 0; j--){
    const num = arr[j];
    if (num < curN && dp1[j] + 1 > dp1[i]) {
      dp1[i] = dp1[j] + 1;
    }
  }
}

for (let i = N - 1; i >= 0; i--){
  const curN = arr[i];
  for (let j = i + 1; j < N; j++){
    const num = arr[j];
    if (num < curN && dp2[j] + 1 > dp2[i]) {
      dp2[i] = dp2[j] + 1;
    }
  }
}

console.log(Math.max(...dp1.map((e, i) => e + dp2[i])) - 1);