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

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

문제 접근

dp문제이다.
n이 최대 1000이기 때문에, 2중 for문을 2번 돌려도 2백만이다. 그래서 시간은 여유가 있다.

cache를 두개로 나누었다. 먼저 앞에서 부터, 증가하는 부분 수열에 대한 정보를 얻었다.
그 후 뒤에서 부터, 감소하는 부분 수열에 대한 정보를 얻었다.
그래서 두 부분 수열을 합하고, 기준이 되는 숫자가 두 번 더해지기 때문에 1을 빼준 수 중 최대값을 구했다.

코드 구현(c++)

#include <iostream>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;
    int dp_min[1001];
    int dp_max[1001];
    int a[1001];

    for(int i = 0 ; i < n ; i++){
        cin >> a[i];
        dp_min[i] = 1;
        dp_max[i] = 1;
    }
    int ans = -1;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < i ; j++){
            if(a[i] > a[j]) dp_max[i] = max(dp_max[j] + 1, dp_max[i]); 
        }
    }

    for(int i = n-1 ; i >= 0 ; i--){
        for(int j = n-1 ; j > i ; j--){
            if(a[i] > a[j]) dp_min[i] = max(dp_min[j] + 1, dp_min[i]);
        }
    }
    for(int i = 0 ; i < n ; i++){
        ans = max(ans, dp_min[i] + dp_max[i] - 1);
    }
    cout << ans << "\n";
}

평가

가장 긴 부분 수열 시리즈를 풀고 있다. 처음에는 dp에 대한 이해가 좀 부족해 어려웠지만, 점점 익숙해지고 있는 거 같다.