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

https://everyyy.tistory.com/75

[백준]11053-가장 긴 증가하는 부분 수열(Dynamic Programming)

11053번 가장 긴 증가하는 부분 수열 문제와 매우 흡사하고, 위 문제를 조금만 변형해면 풀 수 있는 문제이다.

 

우선 똑같이 가장 긴 증가하는 부분 수열을 구한다.

동시에 오른쪽에서 왼쪽으로 가면서 가장 긴 감소하는 부분 수열을 구한다.

 

왼쪽에서 오른쪽으로 이동하며 반환할 후보 변수에 일단 증가, 감소 중 더 큰 값을 할당하고, 그 이후에 검사중인 숫자의 오른쪽에 이 값보다 작은 값이 있는지 확인한다.

있다면 그 값의 감소하는 부분 수열의 길이와 현재 값의 증가하는 부분 수열의 길이를 더한 값이 현재 할당된 반환 후보 변수보다 큰지 확인하고, 크다면 할당한다.

물론 값이 같다면 하나가 줄어드니 1을 뺀다.

 

아래는 코드이다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
 
int part(int N);
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", part(N));
}
 
int part(int N) {
    int** ary = new int* [N];
    for (int i = 0; i < N; i++) {
        ary[i] = new int[4]{ 0, 1, 1, 0 };
        int value;
        scanf("%d", &value);
        ary[i][0] = value;
    }
 
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++) {
            if (ary[i][0] < ary[j][0] && ary[i][1] == ary[j][1])
                ary[j][1]++;
            if (ary[N - i - 1][0] < ary[N - j - 1][0] && ary[N - i - 1][2] == ary[N - j - 1][2])
                ary[N - j - 1][2]++;
        }
    for (int i = 0; i < N; i++) {
        ary[i][3] = ary[i][1] > ary[i][2] ? ary[i][1] : ary[i][2];
        if (ary[i][1] == ary[i][2])
            ary[i][3] = ary[i][1] + ary[i][2] - 1;
        else {
            for (int j = i + 1; j < N; j++)
                if (ary[i][0] >= ary[j][0] && ary[i][3] < ary[i][1] + ary[j][2])
                    ary[i][3] = ary[i][1] + ary[j][2];
        }
    }
        
    int max = 0;
    for (int i = 0; i < N; i++) {
        if (max < ary[i][3])
            max = ary[i][3];
        delete[] ary[i];
    }
    delete[] ary;
    return max;
}