[백준11054_자바스크립트(javascript)] - 가장 긴 바이토닉 부분 수열

🔴 문제

가장 긴 바이토닉 부분 수열

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const [n] = inputs[0];
const A = inputs[1];
const dp = Array.from({ length: n }, () => [1, 1]);
dp[0] = [1, 1];

for (let i = 1; i <= n; i++) {
  for (let j = 0; j < i; j++) {
    if (A[i] > A[j]) {
      dp[i][0] = Math.max(dp[i][0], dp[j][0] + 1);
    } else if (A[i] < A[j]) {
      dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1, dp[j][1] + 1);
    }
  }
}

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

🟢 풀이

⏰ 소요한 시간 : 40분

바이토닉 수열은 증가하면서 감소하는 형태를 허용한다.
따라서 dp배열은 2차원 배열로 만들어 주었다.
dp[0]은 [1, 1]의 값을 갖는데 0번 인덱스는 증가하는 형태일때의 바이토닉 수열 최대 길이이고, 1번 인덱스는 감소하는 형태일 때의 바이토닉 수열 최대 길이이다.
이 후 1부터 n까지의 dp 배열을 채워준다.
dp[i]의 [0]번 인덱스는 증가하는 형태의 바이토닉 수열을 찾아야 하기 때문에 A[i] > A[j]일때의 LIS를 구해주면 된다.
dp[i]의 [0]번 인덱스는 감소하는 형태의 바이토닉 수열을 찾아야 하기 때문에 A[i] < A[j]일때의 LIS를 구해주면 된다. 이 때 증가하는 형태에서 감소하는 형태로 넘어오는 것도 허용 되기 때문에 dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1, dp[j][1] + 1) 세가지 값중 최대값을 구해준다.

🔵 Ref