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

11054. 가장 긴 바이토닉 부분 수열 / c++ / Gold4 / 30분

문제

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

1. 길이가 n인 수열 A가 주어진다.
2. 임의의 지점 Ai를 기준으로 A0 < … < Ai-2 < Ai-1< Ai > Ai+1 > Ai+2 > … > An 의 형태를 취하는 수열을 바이토닉 수열이라고 한다.
3. A에서 가장 긴 바이토닉 부분 수열의 길이는?

접근 방식

동적 프로그래밍

1. dp[i] 는 Arr[i]가 가질 수 있는 가장 긴 증가 부분 수열의 길이
   1. dp[i]는 i보다 왼편의 수 중에서 ‘Arr[i]보다 작은 값 중 dp값이 가장 큰 값’ + 1
2. revDp[i] 는 Arr[i]가 가질 수 있는 가장 긴 감소 부분 수열의 길이
   1. revDp[i]는 i보다 오른편의 수 중에서 ‘Arr[i]보다 작은 값 중 dp값이 가장 큰 값’ + 1
3. dp[i] + revDp[i] 중 가장 큰 값을 반환

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
using namespace std;

inline int MAX(int A, int B) { return A > B ? A : B; }

int N;
int arr[1'000];
int dp[1'000] = {};
int revDp[1'000] = {};

void Print()
{
    for (int i = 0; i < N; ++i)
    {
        cout << dp[i] << ' ';
    }
    cout << '\n';

    for (int i = 0; i < N; ++i)
    {
        cout << revDp[i] << ' ';
    }
    cout << '\n';
}

int DP(int num)
{
    if (dp[num] == 0)
    {
        int maxNum = 0;
        for (int i = 0; i < num; ++i)
        {
            if (arr[i] < arr[num])
                maxNum = MAX(maxNum,DP(i));
        }
        dp[num] = maxNum + 1;
    }
    

    return dp[num];
}

int RevDP(int num)
{
    if (revDp[num] == 0)
    {
        int maxNum = 0;
        for (int i = N-1; i > num; --i)
        {
            if (arr[i] < arr[num])
                maxNum = MAX(RevDP(i), maxNum);
        }

        revDp[num] = maxNum + 1;
    }

    return revDp[num];
}

int Find()
{
    int maxNum = 1;
    for (int i = 0; i < N; ++i)
    {
        maxNum = MAX(maxNum, dp[i] + revDp[i]);
    }

    return maxNum;
}

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

    cin >> N;

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

    for (int i = N - 1; i >= 0; --i)
    {
        RevDP(i);
    }

    cout << Find() - 1 << '\n';

    //Print();

    return 0;
}

다시 생각해 볼 점

1. 역시 테이블로 죽 적어놓고 생각하니 문제풀이가 수월했다.
2. 문제를 두개의 부분문제
   1. 증가 수열의 길이 dp
   2. 감소 수열의 길이 dp

   로 나눠 놓고 나중에 1 + 2 의 값중 제일 큰 값 으로 합쳐서 푸는 사고방식이 중요했다.