BOJ : 11054 가장긴바이토닉부분수열 (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

n = Number(input[0])

let numbers = input[1].split(" ").map(Number)

let dp = []
let dp2 = []

for (let i = 0 ; i < n ; i++){
    dp[i] = 1
    dp2[i] = 1
}

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

for (let i = n-1 ; i >= 0 ; i--){
    for (let j = i+1 ; j < n ; j++){
        if (numbers[i] > numbers[j]){
            dp2[i] = Math.max(dp2[i] , dp2[j]+1)            
        }
        
    }
}

let result = []

for (let i = 0 ; i < dp.length ; i++){
    result[i] = dp[i]+dp2[i]-1
}

c(Math.max(...dp.map((incVal, index) => incVal + dp2[index])) - 1);

 

풀이

처음에 그냥 단순하게 입력값에서 제일 큰 숫자까지 증가된 수열의 길이를 구하고 감소된 길이를 구하면 되는지 알았지만

6
3 2 1 4 5 6
ans: 4

이런 반례에서 통과되지 않기 때문에 다른 방법을 찾아봤습니다.

 

가장 긴 바이토닉 수열을 구하기 위해서 우선, 가장 긴 증가되는 수열과 가장 긴 감소되는 수열을 찾으면 됩니다.

여기서 증가되는 수열은 11053번 풀듯이 구하면 되는데 감소되는 수열을 찾는 방법을 알아야합니다.

감소되는 수열을 찾는 방법은 수열의 뒤에서부터 증가되는 수열을 찾게되면 감소되는 수열을 찾을 수 있습니다.

 

각 인덱스에 증가,감소되는 수열의 갯수를 더한 최대값에서 -1을 해주게 되면 답을 얻을 수 있습니다.

 

-1 해주는 이유는 바이토닉수(?)가 겹치기 때문입니다.

 

문제

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

11054번: 가장 긴 바이토닉 부분 수열