[백준(BOJ] 11054번: 가장 긴 바이토닉 부분 수열 (Dynamic Programming, C++)

📝 문제풀이 과정

---

DP[i]: i번째에서 증가하는 가장 큰 부분수열

DP2[i] : 맨 뒤에서부터 탐색했을 때, i번째에서 가장 큰 증가하는 부분수열

i번째 기준으로 DP[i]와 DP2[i]의 합이 가장 크다면, i번째 기준 이전으로 증가하는 부분수열과, 맨 뒤 기준으로 i번째까지 증가하는 부분수열을 합했을 때 그 수가 가장 큰 것이다.

이때 DP[i]와 DP2[i]에는 i번째가 각각 포함되어 합하게 되면 i번째를 2번 카운팅한 것이 되기 때문에 DP[i] + DP2[i] - 1로 답을 구한다.

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    int S[N] = {}; int DP[N] = {}; int DP2[N] = {};

    for(int i=0; i<N; i++) scanf("%d", &S[i]);

    for(int i=0; i<N; i++){
        DP[i] = 1;
        for(int j=0; j<i; j++){
            if(S[i] > S[j]) DP[i] = max(DP[i], DP[j]+1);
        }        
    }
    for(int i=N-1; i>=0; i--){
        DP2[i] = 1;
        for(int j=N-1; j>i; j--){
            if(S[i] > S[j]) DP2[i] = max(DP2[i], DP2[j]+1);
        }        
    }

    int result=1;
    
    for(int i=0; i<N; i++){
        result = max(result, DP[i] + DP2[i]-1);
    }
    
    printf("%d", result);
}

 

 

👏 결과

---