[C++] 백준 11504: 가장 긴 바이토닉 부분 수열

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

 

이 문제는 '11053. 가장 긴 증가하는 부분 수열 문제' or '11722. 가장 긴 감소하는 부분 수열 문제'를 풀어봤을 경우 매우 간단하게 풀 수 있다.

 

 

<풀이>

바이토닉 수열은 문제의 설명을 읽어봤을 때 증가하는 부분수열 + 감소하는 부분수열이다.

그렇다면 가장 긴 증가하는 바이토닉 수열도 마찬가지라는 뜻이다.

여기서 주의할 점은 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 더해서는 안된다는 것이다.

 

두 수열이 가장 길 때의 시점이 같지 않을 수 있기에,

두 시점의 길이를 저장하는 배열을 따로따로 만들어줘야 한다.

 

 

숫자가 1개 존재할 때도 자기자신으로만 이루어진 수열이므로 모든 dp값의 초기값은 1로 설정한다.

for(int i = 1; i <= n; i++){
        dpIncreasing[i] = dpDecreasing[i] = 1;
    }

 

그 후 각각 가장 긴 증가하는 부분 수열의 배열과 가장 긴 감소하는 부분 수열의 배열을 구해주었다.

for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(num[i] > num[j] && dpIncreasing[i] == dpIncreasing[j]) dpIncreasing[i]++;
        }
    }

    for(int i = n-1; i >= 1; i--){
        for(int j = n; j > i; j--){
            if(num[i] > num[j] && dpDecreasing[i] == dpDecreasing[j]) dpDecreasing[i]++;
        }
    }

 

dpIncreasing[i] == dpIncreasing[j]의 조건을 넣지 않으면 이전의 수열이 가장 긴 증가하는 부분 수열이 아닐 때도 반영되므로 주의하자!!

아래의 경우도 동일하다.

 

두 배열을 구했다면

반복문을 돌려 최댓값을 구하면 된다.

int max = 0;
    for(int i = 1; i <= n; i++){
        int sum = dpIncreasing[i] + dpDecreasing[i];
        if(sum > max) max = sum;
    }

 

 

이 때, 한 지점에서의 길이가 양 측에 모두 더해졌으므로 출력을 할 때 1을 빼준다.

cout<<max-1;

 

 

전체 코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int dpIncreasing[1005];
int dpDecreasing[1005];
int num[1005];

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

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>num[i];
        dpIncreasing[i] = dpDecreasing[i] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(num[i] > num[j] && dpIncreasing[i] == dpIncreasing[j]) dpIncreasing[i]++;
        }
    }

    for(int i = n-1; i >= 1; i--){
        for(int j = n; j > i; j--){
            if(num[i] > num[j] && dpDecreasing[i] == dpDecreasing[j]) dpDecreasing[i]++;
        }
    }

    int max = 0;
    for(int i = 1; i <= n; i++){
        int sum = dpIncreasing[i] + dpDecreasing[i];
        if(sum > max) max = sum;
    }

    cout<<max-1;
    return 0;
}