[알고리즘 문제] 백준11054 - 가장 긴 바이토닉 부분 수열

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

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

바이토닉이라고 처음 들어봤다. 설명에서는 " S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN " 인수라고 한다....

{10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 아니라고 하는데, 아무튼 쭉 오름차순이거나, 쭉 내림차순이거나, 꼭대기를 기준으로 / \ 이런 형태의 수열을 바이토닉 이라고 하는 것 같다.

 

문제 해결은 arr[i]의 값을 기준으로 왼쪽 가장 긴 증가하는 부분 수열 + 오른쪽 가장 긴 감소하는 부분수열값을 dp[i]에 저장한다.

 

마지막에는 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열이 가장 큰 dp[i]를 구한다. 여기서 -1을 해주는 이유는 왼쪽/오른쪽 모두 기본 값이 1인데 이렇게 되면 더할때 1이 2번 더해지기 때문에 1을 빼주었다.

 

check함수의 첫번째 for문은 내림차순, 두번쨰 for문은 오름차순인 경우를 계산하는 코드이다. 

#include <iostream>

using namespace std;

int arr[1001] = {0};
int dp[1001] = {0};
int incDp[1001] = {0};
int decDp[1001] = {0};

int n;

int max(int n1, int n2)
{
    return n1 > n2 ? n1 : n2;
}

void check(int index)
{

    int cnt;

    for (int i = n; i >= index; i--)
    {
        cnt = 0;
        decDp[i] = 1;
        for (int j = i; j <= n; j++)
        {
            if (arr[i] > arr[j])
            {
                cnt = max(cnt, decDp[j]);
            }
        }
        decDp[i] += cnt;
    }

    for (int i = 1; i <= index; i++)
    {
        cnt = 0;
        incDp[i] = 1;

        int cnt2 = 0;

        for (int j = 1; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                cnt = max(cnt, incDp[j]);
            }
        }
        incDp[i] += cnt;
    }
}

int main()
{
    cin >> n;

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

    for (int i = 1; i <= n; i++)
    {
        check(i);
    }

    int result = 0;

    for (int i = 1; i <= n; i++)
    {
        result = max(result, incDp[i] + decDp[i] - 1);
    }

    cout << result;
    return 0;
}