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

문제

백준 11054 문제 보기

접근 방법

먼저 증가하는 부분 수열을 구하는 dp을 작성하고 뒤에서 부터 감소하는 가장 긴 부분 수열을 구하는 dp2를 구한다.
따라서 dp - dp2 - 1에서 최대값을 출력한다. -1을하는 이유는 dp[2] + dp2[2]를 계산하면 2번째 인덱스가 중복 계산되기 때문이다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int N;
int arr[1001];
int dp[1001];
int dp2[1001];

int main() {

    cin >> N;

    memset(arr, 0, sizeof(arr));
    memset(dp, 0, sizeof(dp));
    memset(dp2, 0, sizeof(dp2));

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

    for(int i = 1; i <= N; i ++) {
        dp[i] = 1;
        for(int j = 1; j < i; j ++) {
            if(arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

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

    int ans = 0;
    for(int i = 0; i <= N; i++) {
        if(ans < dp[i] + dp2[i]-1) {
            ans = dp[i] + dp2[i]-1;
        }
    }

    cout << ans;
    return 0;
}