[백준] 11054. 가장 긴 바이토닉 부분 수열(자바스크립트/javascript/js/node.js/동적계획법/다이나믹 프로그래밍/동적 프로그래밍)

 

문제를 풀기 위한 아이디어

앞선 문제 [11053. 가장 긴 증가하는 부분 수열] 에서 조금만 창의적으로 생각하면 풀 수 있는 문제이다.

이 문제는 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열의 합을 구해서 최댓값을 구하면 되는 문제이다.

나는 최대한 헷갈리지 않기 위해서 가장 긴 증가하는 부분 수열을 구해서 값을 저장할 공간을 increaseDP라는 배열을 만들어 값을 저장했고, 가장 긴 감소하는 부분 수열을 구해서 값을 저장할 공간은 decreaseDP라는 배열을 만들어 값을 저장했다.

increaseDP[1] = 1

decreaseDP[N] = 1을 저장한다.

주어진 수열은 numbers라는 배열에 저장한다.

(나는 numbers의 0번째 인덱스에 값을 추가해주었다. 뒤에서 반복문에서 인덱스를 헷갈리지 않게 하기 위해서)

 

그렇게 해서 increaseDP와 decreaseDP의 각각 값을 합쳐준다음 1을 빼준다. 왜냐하면 중간에 기준이 겹치기 때문이다.

그렇게 하여 최댓값을 구해내면 되는 문제이다.

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let numbers = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(numbers[0]);
numbers.shift();
numbers = numbers[0].split(" ").map((element) => Number(element));
numbers.unshift(0);
const increaseDP = new Array(N + 1).fill(1);
const decreaseDP = new Array(N + 1).fill(1);
increaseDP[1] = 1;
decreaseDP[N] = 1;
for (let i = 2; i <= N; i++) {
  const values = [1];
  for (let j = 1; j < i; j++) {
    if (numbers[j] < numbers[i]) {
      values.push(increaseDP[j] + 1);
    }
  }
  increaseDP[i] = Math.max(...values);
}
for (let i = N - 1; i >= 1; i--) {
  const values = [1];
  for (let j = i + 1; j <= N; j++) {
    if (numbers[j] < numbers[i]) {
      values.push(decreaseDP[j] + 1);
    }
  }
  decreaseDP[i] = Math.max(...values);
}
const answer = [];
for (let a = 1; a <= N; a++) {
  answer.push(increaseDP[a] + decreaseDP[a] - 1);
}
console.log(Math.max(...answer));