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

문제는 다음과 같습니다.

이 문제는 제가 바이토닉 수열을 제대로 이해하지 않은 채 풀어서 처음에 삽질을 좀 했습니다..
⚒️항상 문제 제대로 읽기!⚒️

바이토닉 수열이란,
수열이 증가했다가 감소하는 수열을 의미합니다.

저는 증가와 감소를 연속해서 반복하는 수열이라 생각하고 풀다가 시간을 낭비했네요.

음 이 문제도 저는 이전의 최대 부분 증가 수열과 핵심은 같다고 생각합니다.

다만, 여기서는 증가 + 감소가 합쳐져 있으므로,
증가 + 감소가 이루어지는 수열의 최대값은
수열의 i번째 항에 해당하는 수가 변곡점이 되었을 때,
이 수를 기준으로 증가하는 부분수열 + 감소하는 부분수열의 합이 최대가 되어야 합니다.

즉, 입력받은 수열에서

• 가장 긴 증가하는 부분 수열
• 가장 긴 감소하는 부분 수열 (대신 방향은 반대로 구해야 합니다)

이 둘의 합이 최대가 되는 수가 변곡점인 수가 되고,
두 개의 합이 답이 되겠죠?

이 두 개는 동시에 구할수가 없어서 왜냐하면, 감소하는 부분수열의 최대 개수는 오른쪽에서 왼쪽으로 계산해야하기 때문입니다.
저는 처음에 입력받으면서는 증가하는 부분 수열을 구하였고,
이후에 reverse를 이용하여 뒤집은 후에, 감소하는 부분 수열을 구하였습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> a;
    vector<int> inc; vector<int> dec; vector<int> res;

    int n, tmp, tmp_max, j;
    cin>>n;
    cin>>tmp; a.push_back(tmp); inc.push_back(1);

    // 증가수열
    for(int i=1; i<n; i++){
      cin>>tmp; a.push_back(tmp);

      j=i-1;
      tmp_max=0;
      while(j>=0){
        if(a[j]<tmp && inc[j]>tmp_max) tmp_max=inc[j];
        j--;
      }
      inc.push_back(tmp_max+1);
    }

    reverse(a.begin(), a.end());
    // 감소수열
    dec.push_back(1);
    for(int i=1; i<n; i++){
      j=i-1;
      tmp_max=0;
      while(j>=0){
        if(a[j]<a[i] && dec[j]>tmp_max) tmp_max=dec[j];
        j--;
      }
      dec.push_back(tmp_max+1);
    }
    reverse(dec.begin(), dec.end());

    for(int i=0; i<n; i++) res.push_back(inc[i]+dec[i]-1);
    cout<<*max_element(res.begin(), res.end())<<endl;
    return 0;
}