[JavaScript/DP] 백준 골드 4 : 11054 - 가장 긴 바이토닉 부분 수열

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

---

📌 작성한 코드 

// 11054
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const list = input.shift().split(" ").map(Number);

const dp = Array.from({ length: N }, () => new Array(2).fill(0));

for (let i = 0; i < N; i++) {
    dp[i][0] = 1;
    dp[i][1] = 1;

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

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

 

📌 설명 

바이토닉 수열이 되려면 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족해야 한다.

 

✅ 점화식 : dp[i][j] : i번째 숫자를 마지막으로 포함하는 가장 긴 바이토닉 수열의 길이
( j = 0이면 증가하는 단계, j = 1이면 감소하는 단계)

 

바이토닉 수열을 살펴보면 2가지의 단계로 나뉘는데 바로 증가 하는 단계와 감소하는 수열 단계로 나뉜다. 

- 이전 숫자보다 현재 숫자가 크다면 증가하고 있으니 증가하는 부분 수열의 길이를 증가시켜준다.

- 이전 숫자보다 현재 숫자가 작다면 감소하고 있으니 감소하는 부분 수열의 길이를 증가시켜준다.

 

감소하는 부분에서는 2가지 경우가 가능하다.

1. 이전까지는 증가하다가 이번에 감소하게 되는 경우

:  이때 감소하는 부분 수열이 되면 더 이상 증가가 불가능 하다는 의미이므로 이전 숫자가 가진 가잔 긴 증가하는 부분 수열의 길이를 더해준 채로 시작한다.

-> dp[j][0] + 1 부분 

 

2. 이전에도 감소했고 계속해서 감소하게 되는 경우

: 이전 숫자의 감소하는 단계에 이어서 계속 감소하면 된다.

-> dp[j][1] + 1 부분

 

 

✅ 성공