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

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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제

입력
10 
1 5 2 1 4 3 4 5 2 1

출력
7

코드

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

int a[1001];
int d[1001];
int dp[1001];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        d[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1;
        for (int j = n - 1; j >= i; j--) {
            if (a[i] > a[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i<n; i++) {
        if (ans < d[i] + dp[i] - 1) {
            ans = d[i] + dp[i] - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

해결방법

• 수열 안에서 가장 긴 바이토닉 수열을 찾기 위해서는 어느 지점을 기준으로 왼쪽은 증가, 오른쪽은 감소하고 있는 형태를 찾아야 한다.
• 따라서 가장 긴 증가하는 부분수열과, 가장 긴 감소하는 부분수열을 구한 후 기준점을 인덱스로 잡아 해당 위치에서 두 부분수열에 대한 최대값을 찾아 더해준 후 -1을 해주면 된다.
• 기준점은 증가, 감소 부분수열 모두가 공통적으로 취하기 때문에 -1을 꼭 해줘야한다.