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

문제링크 : https://www.acmicpc.net/problem/11054

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[1001];
int dp_plus[1001];
int dp_minus[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        dp_plus[i]=1; //최소길이 1
        for(int j=0; j<i; j++)
        { 
            if(arr[i]>arr[j]) dp_plus[i] = max(dp_plus[i], dp_plus[j]+1); //가장 긴 증가하는 수열 저장
        }
    }

    for(int i=N-1; i>=0; i--)
    {
        dp_minus[i]=1; //최소길이 1
        for(int j=N-1; j>i; j--)
        {
            if(arr[i]>arr[j]) dp_minus[i] = max(dp_minus[i], dp_minus[j]+1); //가장 긴 감소하는 수열 저장
        }
    }

    int result = 0;
    for(int i=0; i<N; i++)
    {
        result = max(result, dp_plus[i] + dp_minus[i]); //가장 긴 바이토닉 수열 저장
    }
    cout << result-1; //중복된 부분 빼주기

    return 0;
}

가장 긴 증가하는 수열과 가장 긴 감소하는 수열을 각각 따로 구해준다.

바이토닉 수열은 증가했다가 다시 감소하는 형태이므로 위에서 구한 각 수열들을 더해주면 된다.

이때 증가의 마지막이자 감소의 시작이 되는 부분은 중복이되기에 -1을 해주면된다.

 

증가하는 수열은 현재값과 그전값들을 비교하며 그전값보다 큰 경우 1을 더해준다.

감소하는 수열은 시작점을 역순으로하여 현재값과 그전값들을 비교하여 그전값보다 큰 경우 1을 더해준다.

(입력받은 수열의 맨 뒤에서부터 증가하는 수열을 찾는 것)

 

이때 주의해야할 것은 기본적으로 수열의 길이가 최소 1이라는 것이다. (자기 자신)

따라서 초기화를 1로 시작하고 해야한다.

<예제>
1 5 2 1 4 3 4 5 2 1

증가하는 수열 (길이 5)
1 x 2 x x 3 4 5 x x

감소하는 수열 (길이 3)
x x x x x x x 5 2 1

중복되는 값 5

5 + 3 - 1 = 7