[BOJ/C+]11054 가장 긴 바이토닉 부분 수열

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

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

---

문제

피라미드 모양과 같이 $S_1<S_2<...<S_{k-1}<S_k>S_{k-1}>...>S_n$을 만족하는 수열을 바이토닉 수열이라 한다. 크기가 n인 수열의 가장 긴 바이토닉 부분 수열을 구해라.

 

풀이

https://lionontheshore.tistory.com/38

[BOJ/C++]11053번 가장 긴 증가하는 부분수열

마찬가지로 이 문제를 응용해 풀었다.

인덱스 i를 기준으로 왼쪽은 1부터 i까지 가장 긴 증가하는 부분 수열의 길이를 계산해 2차원 배열의 0번째 row에 저장하였고, i를 기준으로 오른쪽은 i에서부터 n까지 가장 긴 감소하는부분 수열의 길이를 계산하여 1번째 row에 저장하였다.

 

마지막으로 column의 0번째, 1번째 row를 더하여 최댓값을 구해 가장 긴 바이토닉 부분수열을 구했다.

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int arr[n+1];
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    
    int dp[n+1][2];//올라가는거 0,내려가는거1에 저장
    for(int i=1;i<=n;i++){
        dp[i][0]=1;
        for(int j=1;j<i;j++)
            if(arr[j]<arr[i])
                dp[i][0]=max(dp[i][0],dp[j][0]+1);
    }
    for(int i=n;i>0;i--){
        dp[i][1]=1;
        for(int j=i;j<=n;j++)
            if(arr[i]>arr[j])
                dp[i][1]=max(dp[i][1],dp[j][1]+1);
    }

    int max_num=0;
    for(int i=1;i<=n;i++)
        max_num=max(max_num,dp[i][0]+dp[i][1]);

    cout<<max_num-1<<endl;
}

마지막 num-1은 i 중복계산 된 것