BOJ 11054 가장 긴 바이토닉 부분 수열

boj 11054 가장 긴 바이토닉 부분 수열

boj 11503 가장 긴 증가하는 부분 수열 문제를 풀었다면 쉽게 이해할 수 있는 문제이다. 아래의 풀이를 참고할 것을 추천한다.
boj 11503 가장 긴 증가하는 부분 수열 문제 풀이

바이토닉 수열이 기준이 되는 수를 중심으로 증가하는 수열에서 감소하는 수열로 바뀐다는 것에 포인트를 잡았다.
바이토닉 수열의 길이의 최댓값 = (기준 수까지 증가하는 수열 길이 + 기준 수부터 감소하는 수열 길이)의 최댓값라고 이해할 수 있다.
Dinc[i]는 i를 마지막 원소로하는 증가 수열 길이의 최댓값이고, Ddec[i]는 시작 원소를 i로 하는 감소 수열 길이의 최댓값이다. 쉽게 구현하기 위해 Ddec[i] 표현을 달리해보자. 수열이 담긴 배열 a[i]를 거꾸로 끝에서부터 탐색한다고 하면, Ddec[i]도 i를 마지막 원소로하는 증가 수열 길이의 최댓값이라고 정의할 수 있다. 문제에 주어진 예시를 바탕으로 그림으로 나타내보겠다.

Dsum[i] = Dinc[i] + Ddec[i] 이다. 기준 수의 길이가 두번 더해지므로 Dsum[i]에서 1을 빼줘야 문제에서 구하고자 하는 바이토닉 수열 길이의 최댓값이 된다. 위 내용을 바탕으로 구현한 코드를 보자.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[1005];
int Dinc[1005];
int Ddec[1005];
int Dsum[2005];
int ans;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        Dinc[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (a[i] > a[j] && Dinc[j] >= Dinc[i])
                Dinc[i] = Dinc[j] + 1;
        }
    }

    for (int i = n; i >= 1; i--)
    {
        Ddec[i] = 1;
        for (int j = n; j > i; j--)
        {
            if (a[i] > a[j] && Ddec[j] >= Ddec[i])
                Ddec[i] = Ddec[j] + 1;
        }
        Dsum[i] = Dinc[i] + Ddec[i];
        ans = max(ans, Dsum[i]);
    }

    cout << ans - 1;
}