[boj] 11054. 가장 긴 바이토닉 부분 수열 (node.js)

문제

[boj] 11054. 가장 긴 바이토닉 부분 수열 (node.js)

풀이

• 특정 수를 기준으로 좌측, 우측 수들을 항상 증가하는 부분 수열이 되도록 고를 수 있다.

  수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

• 이를 LIS(하단 풀이의 dynamic() 함수 참조)를 순방향, 역방향으로 구한 후 더해주는 방식으로 구현했다. 이때, 결과를 더해줄 때 기준이 되는 수를 2번 세게 되므로 1 빼주어야 한다.

  const forward = dynamic();
  arr.reverse();
  const reversed = dynamic();
  
  let result = 0;
  for (let i = 0; i < N; i++) {
    result = Math.max(forward[i] + reversed[N - 1 - i], result);
  }
  console.log(result - 1);

생각

• 처음에 LIS 문제를 강의를 보고 이해한 후, 응용 문제를 여러 개 풀면서 유형을 익혔다. 새로운 문제가 나와도, 기존 문제 풀이법과 크게 달라지지 않는 접근으로 시작하면 수월히 풀릴 수 있어 재밌게 풀었다.
• 다만, 어느정도 시간을 두고 푼 게 아니라 1주 사이에 같은 유형을 계속 익혔기 때문에 한 번 잊으면 또 못 풀이하게 될 수 있다. 지금까지 풀어온 문제들을 되짚어보며 dp 문제들의 스스로 유형화해보고 넘어가는 게 좋겠다.

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = input();
  const arr = input().split(" ").map(Number);
  const forward = dynamic();
  arr.reverse();
  const reversed = dynamic();

  let result = 0;
  for (let i = 0; i < N; i++) {
    result = Math.max(forward[i] + reversed[N - 1 - i], result);
  }
  console.log(result - 1);

  function dynamic() {
    const dp = [];
    for (let i = 0; i < N; i++) {
      if (!dp[i]) dp[i] = 1;
      for (let j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }
    return dp;
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});