[Algorithm] Baekjoon 11054번 : 가장 긴 바이토닉 부분수열

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

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

 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int inputs[1001] = { 0 };
    int increaseDP[1001] = { 0 };
    int decreaseDP[1001] = { 0 };
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> inputs[i];
    }
 
    for (int i = 0; i < n; i++)
    {
        int maxNum = 0;
        increaseDP[i] = 1;
 
        for (int j = 0; j < i; j++)
        {
            if (inputs[j] < inputs[i])
            {
                maxNum = max(maxNum, increaseDP[j]);
            }
        }
 
        increaseDP[i] += maxNum;
    }
 
    for (int i = n-1; i >= 0; i--)
    {
        int maxNum = 0;
        decreaseDP[i] = 1;
 
        for (int j = n-1; j > i; j--)
        {
            if (inputs[j] < inputs[i])
            {
                maxNum = max(maxNum, decreaseDP[j]);
            }
        }
 
        decreaseDP[i] += maxNum;
    }
 
    int answer = 0;
 
    for (int i = 0; i < n; i++)
    {
        answer = max(answer, increaseDP[i] + decreaseDP[i] - 1);
    }
 
    cout << answer;
}

 

증가했다가 내려가는 형태의 수열을 바이토닉 부분수열이라 한다.

각 인덱스마자 증가부분수열dp, 감소부분수열dp를 따로 테이블업데이트를 해 준 뒤,

마지막에 두 dp값을 더한값 중 큰 값을 출력하면 된다.

-1을 해주는 이유는 각 테이블에 업데이트할 때 기준인덱스자신을 포함한 값으로 업데이트 했기 때문이다.

테이블이 두개라서 자기자신이 두번포함됐기 때문에 -1을 해줘야 한다.