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

가장 긴 바이토닉 부분 수열

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

<코드>

#include <stdio.h>
 
int main(void){
    int N;
    int Dp[2][1010] = {};
    int A[1010] = {};
    int max = 0;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &A[i]);
 
    for (int i = 1; i <= N; i++)
    {
        int maxA = 0;
        for (int j = 0; j < i; j++){
            if (A[i]>A[j]){
                if (maxA < Dp[0][j])
                    maxA = Dp[0][j];
            }
        }
        Dp[0][i] = maxA + 1;
    }
 
    
    for (int i = N; i >= 1; i--)
    {
        int maxA = 0;
        for (int j = N; j > i; j--){
            if (A[i]>A[j]){
                if (maxA < Dp[1][j])
                    maxA = Dp[1][j];
            }
        }
        if (Dp[1][i]<maxA + 1)
            Dp[1][i] = maxA + 1;
    }
    
    for (int i = 1; i <= N; i++){
        if (max < Dp[0][i] + Dp[1][i])
            max = Dp[0][i] + Dp[1][i];
    }
 
 
    printf("%d\n", max-1);
 
}

<문제 푼 요령>

1. 이건 '가장 긴 증가하는 부분 수열'을 두 번 사용해서 풀면 된다.

2. -> 오른쪽 방향으로 진행을 한번 하고 <- 왼쪽 방향으로 진행을 하여서 그 두개의 Dp 배열의 합이 최대가 되는 곳이 가장 긴 바이토닉 수열이 되는 것이다.

3. 하지만 자기자신을 둘다 가지고 있기 때문에 -1값을 해야한다.