[11053번] 가장 긴 증가하는 부분수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘

http://www.crocus.co.kr/429의 내용을 그대로 이용한다면 해결 할 수 있다.

이 내용을 이해하기 전에 LIS가 무엇인지, LIS를 언제 이용하는지를 알아야 하는 것은 본인의 몫이다.

LIS 알고리즘

이 알고리즘의 원칙은 다음과 같다.

1. lis 배열에 아무 값이 없다면 조사 하는 배열(arr)의 첫번째 값을 넣는다.

2. lis 배열의 가장 큰 값(가장 오른쪽에 있는 값) 보다 현재 보고 있는 arr[i] 값이 크다면 lis배열에 arr[i]값을 추가한다.

3. 그 외에는 lower_bound(주어진 집합의 어떤 원소보다 작거나 같은 원소라는 뜻)을 이용하여 그 위치에 값을 넣어준다.

소스 코드 : 

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
 
int _lower_bound(int start, int end, int *arr, int target)
{
    int mid;
    while (end - start > 0)  // 주어진 범위[start,end]에서 탐색하도록 한다. start == end이면 반복 종료
    {
        mid = (start + end) / 2;  // 주어진 범위의 중간 위치를 계산한다
 
        if (arr[mid] < target) // 찾고자 하는 값보다 작으면 오른쪽으로 한 칸만 더 시작 구간 갱신
            start = mid + 1;
 
        else  // 찾고자 하는 값보다 크면 거기까지 끝 구간 갱신
            end = mid;
    }
    return end + 1; // 찾는 구간에 없는 경우 가장 마지막 +1 위치 전달
}
 
 
int main()
{
    int i, n, j = 0;
    int cnt = 0;
    int lis[1001];
    int arr[1001];
    
    scanf("%d", &n);
 
    for (i = 0; i<n; ++i)
        scanf("%d", &arr[i]);
    
    i = 0;
 
    lis[i] = arr[i];
    i++;
 
    while (i < n)
    {
        // lis의 가장 큰 값보다 더 큰값이 들어오면
        if (lis[j] < arr[i])
        {
            lis[j + 1] = arr[i];
            j++;
        }
 
        else
        {
            int ans = _lower_bound(0, j, lis, arr[i]);
            lis[ans - 1] = arr[i];
        }
 
        i++;
    }
    
    printf("%d", j + 1);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>