[BOJ] 11054 - 가장 긴 바이토닉 부분 수열 (C++)

문제

가장 긴 바이토닉 부분 수열

코드

#include <iostream>

using namespace std;

int N, m = 0;
int arr[1001], l[1001], r[1001];

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

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

    // from left
    for (int i = 0; i < N; i++){
        l[i] = 1;
        for (int j = 0; j < i; j++){
            if (arr[i] > arr[j]){
                l[i] = max(l[i],  l[j]+1);
            }
        }
    }

    // from right 
    for (int i = N-1; i >= 0; i--){
        r[i] = 1;
        for (int j = N-1; j > i; j--){
            if (arr[i] > arr[j]) {
                r[i] = max(r[i], r[j]+1);
            }
        }
    }

    for (int i = 0; i < N; i++) m = max(m, l[i]+r[i]-1);
    
    cout << m;
    return 0;
}

접근

문제에서 바이토닉 수열의 정의와 예시를 보고 일정하게 증가하거나, 감소하거나, 증가하다가 한번만 감소하는 형태를 이루는 것을 알 수 있었다. 이 부분에서 첫 번째 인덱스와 마지막 인덱스를 기준으로 증가하는 수열의 길이를 저장하고 이를 더하고 1을 뺀 것이 바이토닉 수열의 길이가 되는 것이라고 생각했다. 1을 뺀 이유는 좌, 우로 두 번 포함되기 때문이다. 따라서 이 아이디어를 구현하기 위해 스택에 넣는 방법도 떠올랐지만 입력 배열의 길이가 1000정도 인 것을 보고 브루트 포스하게 값을 갱신해도 괜찮을 것이라는 생각이 들었다. 이를 바탕으로 코드를 작성하였다.