[C++] BOJ 11054번: 가장 긴 바이토닉 부분 수열

문제 링크

풀이 설명

DP를 이용하여 문제를 해결하였다. 증가하는 부분 수열에 대한 DP값을 저장하는 dp1과 바이토닉 부분 수열에 대한 DP값을 저장하는 dp2 수열로 나누어 각각의 값을 계산하였다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1004];
int dp1[1004]; // 증가 부분 dp
int dp2[1004]; // 증가하다 감소 부분 dp
int result;

void calcDp()
{
    for (int i = 0; i < N; i++)
    {
        int maxdp1 = 0;
        int maxdp2 = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[j] < arr[i])
                maxdp1 = max(maxdp1, dp1[j]);
            else if (arr[j] > arr[i])
                maxdp2 = max(max(maxdp2, dp2[j]), dp1[j]);
        }
        dp1[i] = maxdp1 + 1;
        dp2[i] = maxdp2 + 1;
        result = max(result, dp2[i]);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

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

    calcDp();

    cout << result << '\n';

    return 0;
}