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

문제 주소

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

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

알고리즘

DP

힌트

i위치까지 가장 긴 증가하는 부분수열의 길이와 i위치까지 가장 긴 감소하는 부분 수열의 길이를 구한다.

문제풀이

dp[i][0]에 i위치까지 가장 긴 증가하는 부분수열의 길이 dp[i][1]에 i위치까지 가장 긴 감소하는 부분 수열의 길이를 저장하고 두 합이 가장 큰 것의 값을 구한다.

#include<iostream>
using namespace std;
int in[1002];
int dp[1002][2];

int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>in[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(in[i]>in[j])
                dp[i][0]=max(dp[i][0],dp[j][0]+1);
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=n+1;j>i;j--){
            if(in[i]>in[j])
                dp[i][1]=max(dp[i][1],dp[j][1]+1);
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        //cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<"\n";
        ans=max(ans,dp[i][0]+dp[i][1]);
    }

    cout<<ans-1;

}

 

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