[DP] 가장 긴 바이토닉 부분 수열 (백준 11054번)

 

문제 자체는 어렵지 않다, 떠올리는 발상이 좀 오래 걸릴 수 있긴 하지만,

생각을 해냈다면 그 이후는 크게 어려울 것도 없다.

 

나 같은 경우에는, 하나의 index를 기준으로

좌측과 우측으로 각각 내림차순으로 최장 길이 수열을 구하고, 그 둘의 합을 하나의 dp에 저장할 것이다.

 

#include <iostream>
using namespace std;
 
int list[1000];
int dp[1000][3];
int n;
 
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> list[i];
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
 
            if (j < i && list[j] < list[i] && dp[i][0] < dp[j][0]+1) dp[i][0] = dp[j][0] + 1;
        }
    }
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            if (i == j) continue;
 
            if (i < j && list[i] > list[j] && dp[i][1] < dp[j][1] + 1) dp[i][1] = dp[j][1] + 1;
        }
    }
 
//    for (int i = 0; i < n; i++)
//    {
//        cout << dp[i][0] << ' ' << dp[i][1] << endl;
//    }
 
    
    int maxV = -1;
    for (int i = 0; i < n; i++)
    {
        dp[i][2] = dp[i][0] + dp[i][1] + 1;
        if (maxV < dp[i][2]) maxV = dp[i][2];
    }
 
    cout << maxV;  
}

그래서 배열 dp가 [][3]의 꼴로 선언되어 있다.

0과 1의 합을 dp[2]에 저장해서 이 값들만 비교해서 최대값을 출력해주었다.