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

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

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

 

 

 

EXPLANATION

 

11053 가장 긴 증가하는 부분 순열 문제(풀이 보러가기)와 원리가 똑같다.

11503 문제는 증가만하는 수열의 경우 비교하면 된지만

이 문제는 그 경우들의 수열의 마지막 수를 기준으로 다시 감소하는 수열을 이어서 최종적으로 만들어지는 수열의 경우를 비교한다.

결국, 1<=i <=N의 각 1부터 i번째까지의 숫자들 중에서 i번째 숫자를 포함해서 가장 긴 증가하는 수열의 길이를 구하고

반대로, 각 N부터 1번째까지의 숫자들 중에서 원래 i번째 숫자를 포함해서 가장 긴 증가하는 수열의 길이를 구해서 합친 값에 -1을 하면(i번째 숫자가 수열에 2번 중복되지 않도록)

i번째 숫자를 포함하는 가장 긴 바이토닉 부분 수열의 길이가 된다.

이것을 dp[i]라고 하고 1<= i <=N의 모든 dp[i] 중에서 최댓값이 답이 된다.

 

앞에서부터 i번재까지 갱신

for(int i = 1; i <= N; i++){

    dp1[i] = 1;
    for(int j = 1; j < i; j++){
        if(arr[i] > arr[j]){
            dp1[i] = max(dp1[i], dp1[j] + 1);
        }
    }
}

 

뒤에서부터 원래 i번째까지 갱신

for(int i = N; i >0; i--){ 

    dp2[i] = 1;
    for(int j = N; j > i; j--){
        if(arr[i] > arr[j]){
            dp2[i] = max(dp2[i], dp2[j] + 1);
        }
    }
}

 

이렇게 구해진 dp1[i]+dp2[i] - 1이 dp[i]

1<=i<=N의 dp[i]들을 모두 비교해서 가장 큰 것이 답

 

 

 

CODE

#include <iostream>
using namespace std;

int main(){
    int N;
    int maxV = 0;
    int arr[1001] = {};    //for[1, N]
    int dp1[1001] = {};
    int dp2[1001] = {};
    
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    } 

    for(int i = 1; i <= N; i++){
        
        dp1[i] = 1;
        for(int j = 1; j < i; j++){
            if(arr[i] > arr[j]){
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }
    }
    for(int i = N; i >0; i--){ 
        
        dp2[i] = 1;
        for(int j = N; j > i; j--){
            if(arr[i] > arr[j]){
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
    }
    for(int i = 1; i <= N; i++){
        maxV = max(maxV, dp1[i]+dp2[i] -1);
    }
    cout << maxV << " ";
}