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

  바이토닉 수열이라는 명칭이 되게 생소하긴 하지만 개념 자체는 어렵지 않았다. 바이토닉 부분 수열을 선 그래프로 그렸을 때 깔끔하게 산 모양이 나오면 되는거다! (물론 값이 극단적이면 깔끔하진 않겠지...)

 

  아무튼 나는 이 문제를 11053번 : 가장 긴 증가하는 부분 수열의 응용으로 풀었다. 아쉽게도 내 블로그에는 11053번의 풀이가 없어서 11053번의 약간 심화 문제인 14002번 : 가장 긴 증가하는 부분 수열 4의 풀이법을 링크 걸어둔다.

 

문제의 예시를 표로 표현하면 그림과 같다.

  개념은 다음과 같다. 가장 긴 증가하는 부분 수열을 정순(앞에서부터) 구해서 len이라는 배열에 저장해둔다. 그리고 역순(뒤에서부터)으로 한 번 더 구해서 revLen이라는 배열에 저장해둔다. 그리고 마지막에 len + revLen - 1의 값이 제일 큰 것이 제일 긴 바이토닉 부분 수열의 길이다. 1을 빼는 이유는 기준이 되는 제일 큰 숫자가 2번 세지기 때문이다.

 

#include <stdio.h>
#include <iostream>
 
using namespace std;

int n;
int seq[1004];
int len[1004];
int revLen[1004];

int main()
{
    cin >> n;
    
    for(int i = 0; i <= n; i++)
    {
        cin >> seq[i];
    }
    
    len[0] = 1;
    
    for(int i = 1; i < n; i++)
    {
        len[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(seq[j] >= seq[i]) continue;
            if(len[i] > len[j] + 1) continue;
            
            len[i] = len[j] + 1;
        }
    }
    
    revLen[n - 1] = 1;
    
    for(int i = n - 2; i >= 0; i--)
    {
        revLen[i] = 1;
        for(int j = n - 1; j > i; j--)
        {
            if(seq[j] >= seq[i]) continue;
            if(revLen[i] > revLen[j] + 1) continue;
            
            revLen[i] = revLen[j] + 1;
        }
    }
    
    int ans = 0;
    
    for(int i = 0; i < n; i++)
    {
        ans = max(ans, len[i] + revLen[i] - 1);
    }
    
    cout << ans;
 
    return 0;
}