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

문제 출처 :

https://www.acmicpc.net/problem/11054

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘, 가장 긴 증가하는 부분 수열 :: http://www.crocus.co.kr/582

2. LDS 알고리즘, 가장 긴 감소하는 부분 수열 :: http://www.crocus.co.kr/669

3. LIS와 LDS의 조합

사실 LDS라는 말은 없지만 LIS와 반대로 동작하는 알고리즘을 설명하기 위해 LDS라고 지칭하겠다.

lis 알고리즘을 알고, lis를 역으로 이용할 수 있는 lds 알고리즘을 코딩하면 90%는 완료됐다.

만약 1 5 2 1 4 3 4 5 2 1 라는 배열이 있다면

바이토닉 수열을 구하기 위해서는

1 | 5 2 1 4 3 4 5 2 1

1 5 | 2 1 4 3 4 5 2 1

1 5 2 | 1 4 3 4 5 2 1

1 5 2 1 | 4 3 4 5 2 1

1 5 2 1 4 | 3 4 5 2 1

1 5 2 1 4 3 | 4 5 2 1

1 5 2 1 4 3 4 | 5 2 1

1 5 2 1 4 3 4 5 | 2 1

1 5 2 1 4 3 4 5 2 | 1

이렇게 구분선을 두어 왼쪽 lis 오른쪽 lds를 구하면 된다.

왼쪽 lis, 오른쪽 lds를 보자.

1 | 5 2 1 4 3 4 5 2 1  lis :: 1 lds :: 5 max :: 6

1 5 | 2 1 4 3 4 5 2 1  lis :: 2 lds :: 4 max :: 6

1 5 2 | 1 4 3 4 5 2 1  lis :: 2 lds :: 4 max :: 6

1 5 2 1 | 4 3 4 5 2 1  lis :: 2 lds :: 4 max :: 6

1 5 2 1 4 | 3 4 5 2 1  lis :: 3 lds :: 3 max :: 6

1 5 2 1 4 3 | 4 5 2 1  lis :: 3 lds :: 3 max :: 6

1 5 2 1 4 3 4 | 5 2 1  lis :: 4 lds :: 3 max :: 7

1 5 2 1 4 3 4 5 | 2 1  lis :: 5 lds :: 2 max :: 7

1 5 2 1 4 3 4 5 2 | 1  lis :: 5 lds :: 1 max :: 6

따라서 max (DP)는 7이 된다.

이렇게 | 구분자를 split라는 변수로 두어 lis와 lds의 구분 시작점을 나타내었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#define max(a, b)(a > b ? a : b)
 
using namespace std;
 
int arr[1001];
int lds[1001];
int lis[1001];
 
int DP;
 
int lis_lower_bound(int start, int end, int target)
{
    int mid;
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lis[mid] < target)
            start = mid + 1;
 
        else
            end = mid;
    }
    return end + 1;
}
 
int lds_lower_bound(int start, int end, int target)
{
    int mid;
 
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lds[mid] > target)
            start = mid + 1;
        else
            end = mid;
    }
    return end + 1;
}
 
int main()
{
    int n;
    int pArr, pLis, pLds;
    int split = 1;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    for (int i = 0; i < n - 1; i++)
    {
        memset(lis, 0, sizeof(lis));
        memset(lds, 0, sizeof(lds));
 
        pArr = 1, pLis = 0;
        lis[pLis] = arr[0];
 
        while (pArr < split)
        {
            if (lis[pLis] < arr[pArr])
                lis[++pLis] = arr[pArr];
 
            else
            {
                int pos = lis_lower_bound(0, pLis, arr[pArr]);
                lis[pos - 1] = arr[pArr];
            }
 
            pArr++;
        }
 
        pArr = split-1, pLds = 0;
        lds[pLds] = arr[split];
        while (pArr < n)
        {
            if (lds[pLds] > arr[pArr])
                lds[++pLds] = arr[pArr];
 
            else
            {
                int pos = lds_lower_bound(0, pLds, arr[pArr]);
                lds[pos - 1] = arr[pArr];
            }
 
            pArr++;
        }
    
        split++;
        DP = max(DP, pLis +  pLds + 1);
    }
    
    printf("%d", DP);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>