BOJ 11054 - 가장 긴 바이토닉 부분 수열 (C++)

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

문제를 푼 날짜: 2025. 06. 03

#dp

아이디어

• 각 인덱스를 기준으로 "증가"하는 부분 수열과, "감소"하는 부분 수열을 각각 계산해서 합치는 방식.
• DP(동적 프로그래밍)를 두 번 적용!
• DP1[i] : i번째 원소까지 고려했을 때, 해당 원소를 끝으로 하는 가장 긴 증가 부분 수열의 길이
• DP2[i] : i번째 원소부터 시작해서, 해당 원소를 시작으로 하는 가장 긴 감소 부분 수열의 길이 (뒤에서부터 거꾸로!)
• DP2를 '뒤에서부터 센 가장 긴 증가 부분 수열'로 생각.
• 각 인덱스 i에 대해 DP1[i] + DP2[i] - 1 (-1 하는 이유는 i가 중복 포함되니까!)
• 이 값의 최댓값이 곧 가장 긴 바이토닉 부분 수열의 길이

내 풀이(C++)

#include <iostream>

using namespace std;

int A[1010];
int DP1[1010];
int DP2[1010];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int max;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> A[i];

        max = 0;
        for(int j = 0; j < i; j++){
            if(A[j] < A[i] && DP1[j] > max) max = DP1[j];
        }
        DP1[i] = max + 1;
    }

    for(int i = N-1; i >= 0; i--){
        max = 0;
        for(int j = N -1; j > i; j--){
            if(A[i] > A[j] && DP2[j] > max) max = DP2[j];
        }
        DP2[i] = max + 1;
    }

    max = 0;

    for(int i = 0; i < N; i++){
        if(DP1[i] + DP2[i] > max) max = DP1[i] + DP2[i];
    }

    cout << max - 1;
    return 0;
}