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

문제

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

예제 입력 1 

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1 

7

문제 풀이

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

int n, ans=0;
int arr[1001];
int arr_inc[1001];
int arr_dec[1001];
int main(){

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

    for(int i = 0; i < n; i++)
    {
	arr_inc[i] = 1;
	for(int j = 0; j < i; j++)
	    if(arr[i] > arr[j])
		    arr_inc[i] = max(arr_inc[i], arr_inc[j] + 1);
    }

    for(int i = n - 1; i >= 0; i--)
    {
	arr_dec[i] = 1;
	for(int j = n - 1; j > i; j--)
	    if(arr[i]>arr[j])
		    arr_dec[i] = max(arr_dec[i], arr_dec[j] + 1);
    }
    int sum;
    for(int i = 0; i < n; i++){
	sum = arr_dec[i] + arr_inc[i];
	ans = max(ans, sum);
    }

    cout << ans - 1 << endl;
    return 0;
}

아이디어

주어진 수열에서 오름차순과 내림차순을 동적 계획법으로 계산해주고 마지막 for문에서 i번째의 오름차순 된 arr과 내림차순 된 arr을 더한 가장 큰 값을 구해 -1해준다. -1을 해주는 경우는 오름차순의 원소와 내림차순의 원소가 중복되어서 1을 빼워야한다.