[Gold 4] 11054 가장 긴 바이토닉 부분 수열

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

 

바이토닉 부분 수열은 DP를 사용해 구할 수 있다.

바이토닉 부분 수열을 살펴보면 

증가하는 수열 부분과 감소하는 수열 부분이 있다는 것을 알 수 있다.

이는 A[i]까지 증가하는 부분 수열과 A[i]부터 감소하는 부분 수열을 구하면 된다는 것을 알 수 있다.

 

A[i]까지 증가하는 부분 수열은 다음과 같이 구한다.

// 증가하는 수열 중 가장 긴 것
    for(int i = 0;i<N;i++){
        dp[i] = 1;
        for(int j = 0;j<=i;j++){
            if(A[j] < A[i] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
    }

 

초기 A[i]인 경우 부분 수열의 길이는 1이 되므로 dp[i]를 1로 초기화한다.

이후 0번째 인덱스부터 i 번째 인덱스까지 A배열에 존재하는 값을 비교한다.

A[i] 기준으로 이전에 존재하는 값들이 작고

dp[i]의 값이 이전에 존재한는 값들의 dp보다 작은 경우

dp[i]를 갱신하게 된다. 

 

감소하는 부분 수열은 증가하는 부분 수열과 유사하다.

 

#include <iostream>
using namespace std;

int N;
int A[1000];

int dp[1000];
int rdp[1000];
int answer = 0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    for(int i = 0;i<N;i++)
        cin>>A[i];
    
    // 증가하는 수열 중 가장 긴 것
    for(int i = 0;i<N;i++){
        dp[i] = 1;
        for(int j = 0;j<=i;j++){
            if(A[j] < A[i] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
    }

    // 감소하는 수열 중 가장 긴 것
    for(int i = N-1;i>=0;i--){
        rdp[i] = 1;
        for(int j = N-1;j>=i;j--){
            if(A[i] > A[j] && rdp[j] + 1 > rdp[i])
                rdp[i] = rdp[j] + 1;
        }
    }

    for(int i = 0;i<N;i++)
        answer = max(answer,dp[i] + rdp[i] - 1);
    
    cout<<answer;
}