BOJ 11054 : 가장 긴 바이토닉 부분 수열

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

Baekjoon Online Judge스타트링크 (Startlink)

이 문제는 알고보면 상당히 간단한 문제이다.

해당 문제에서 처음에 주어진 설명을 보면

예를 들어, {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} 은 바이토닉 수열이 아니다.

이렇게 설명이 되어있는데  여기서 바이토닉 수열인 부분을 살펴보게 되면
10, 20, 30, 25, 20 에서 10, 20, 30 까지는 증가를 하고 30, 25, 20 부분은 감소를 한다는 것을 알 수 있다.  

LIS 알고리즘을 다뤄보았는 사람이라면 알겠지만 하나의 바이토닉 수열은 증가하는 부분수열과 감소하는 부분수열으로 이루어져있다는 것을 알 수 있고
LIS 알고리즘을 정방향으로 저장하며 진행을 하고 한번은 역방향으로 다른 배열에 저장하며 진행을 한다면

[1, 2, 3, 1 ,1]-정방향
[1, 1, 3, 2, 1]-역방향

이런식으로 양측에서 가장 긴 증가/감소하는 수열을 찾을 수 있게 된다.

이제 이 문제를 보면 수열 전체에서 바이토닉 수열인 부분을 구하기 위해 LIS 알고리즘을 정방향/역방향으로 진행시키고 같은 위치의 LIS 값을 더한 최대값을 구하도록 하면 같은 위치이기에 생기는 중복된 하나의 숫자를 지우기 위해 -1을 한 값이 가장 긴 바이토닉 부분 수열이 되는 것이다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int arr[1003],g[1003]={0,},f[1003]={0,};
int main()
{
    int n,i,j,mx=-999;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
    for(i=0;i<n;i++)
    {
        if(!g[i])g[i]=1;
        for(j=0;j<i;j++)
            if(arr[i]>arr[j]&&g[i]<g[j]+1)g[i]++;

    }
    for(i=n-1;i>=0;i--)
    {
        if(!f[i])f[i]=1;
        for(j=n-1;j>=i;j--)
             if(arr[j]<arr[i]&&f[i]<f[j]+1)f[i]++;
    }
    for(i=0;i<n;i++)
        mx=max(mx,g[i]+f[i]-1);
    printf("%d",mx);
    return 0;
}