[11722번] 가장 긴 감소하는 부분 수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. lis 알고리즘 :: http://www.crocus.co.kr/583

2. lis 응용 -> lds ( Longest Decreasing Subsequence )

사실 lds 같은 알고리즘은 존재하지 않는다.

lis 알고리즘을 정확히 이해하고 있다면  증가하는 가장 긴 부분 수열을 만들거나, 

감소하는 가장 긴 부분 수열을 자유로이 만들 수 있다.

이 문제는 원래 DP로 푸는 문제라고 명시되어있으나, lis 알고리즘 또한 DP의 일종이므로 lis 알고리즘을 응용하여 풀어보자.

1 3 2 4 5가 있다면 lis는 1 2 4 5를 찾아준다.

5 3 1 2 4가 있다면 lds는 5 3 2를 찾아준다.

결국 lis를 거꾸로만 해주면 된다는 의미이다. 위의 링크를 통해 lis 알고리즘에 대해 명확히 이해하고 이를 접목시켜보자.

lis 알고리즘을 이해했는지 물어보기에 좋은 문제인 것 같다.

 

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int arr[1001];
int lds[1001];
 
int _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;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int pArr = 1, pLds = 0;
 
    lds[pLds] = arr[0];
 
    while (pArr < n)
    {
        if (lds[pLds] > arr[pArr])
            lds[++pLds] = arr[pArr];
 
        else
        {
            int pos = _lower_bound(0, pLds, arr[pArr]);
            lds[pos - 1] = arr[pArr];
        }
 
        pArr++;
    }
    printf("%d", pLds + 1);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>