[JavaScript] 백준 11054 가장 긴 바이토닉 부분 수열 (JS)

가장 긴 바이토닉 부분 수열

📚 문제 설명

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
수열 A 가 주어질 때, A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이는 몇인가 ?

👨🏻‍💻 풀이 과정

이 문제는 백준 11053 가장 긴 증가하는 부분 수열과 거의 똑같은 문제이다.
두 문제에서 사용하는Dp 배열의 핵심은 각각의 원소를 기준으로 왼쪽에서 순서대로 오름차순이 되는 부분 수열의 길이를 저장하는 것이다.

• input으로 받은 수열의 길이와 같은 길이의 Dp 배열 생성, 1로 초기화.
• 2중 for문을 이용, input[i]의 원소 기준 왼쪽을 순서대로 확인.
  • UpDp[i] = Math.max(UpDp[i], UpDp[j] + 1);

이렇게 갱신하면 UpDp[i]는 input[i]가 마지막 원소인 부분 수열의 크기가 저장된다.

이를 이용하여 input[i]를 시작으로 하는 내림차순 부분수열을 구하여 Updp 와 합치면 된다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
    input = input.shift().split(' ').map(Number);
    let UpDp = new Array(N).fill(1);
    let DownDP = new Array(N).fill(1);
    let answer = 0;

	// 오름차순 부분수열
    for (let i = 1; i < UpDp.length - 1; i++) {
        for (let j = 0; j < i; j++) {
            if (input[i] > input[j]) {
                UpDp[i] = Math.max(UpDp[i], UpDp[j] + 1);
            }
        }
    }
	// 내림차순 부분수열
    for (let i = DownDP.length - 2; i >= 0; i--) {
        for (let j = DownDP.length - 1; j > i; j--) {
            if (input[i] > input[j]) {
                DownDP[i] = Math.max(DownDP[i], DownDP[j] + 1);
            }
        }
    }
	// 두 배열을 합쳐서 최댓값 갱신.
    UpDp.forEach((value, index) => {
        answer = value + DownDP[index] > answer ? value + DownDP[index] : answer;
    });
	// 두 배열을 합쳤기 때문에 input[i]가 2번 들어간 길이가 나온다. 따라서 -1 진행.
    console.log(answer - 1);

🧐 후기

for 문 1개 안에 2개의 for 문을 담아서 풀려고 고민했는데 그렇게 되면 오름차순 배열과 내림차순 배열은 서로 다른 방향에서 갱신을 진행하여 DP 배열이 갱신되어야 하지만 만약 처음 for 문을 왼쪽부터 진행할 경우 DownDP를 갱신할 때 문제가 생긴다.