BOJ 1818 - 책정리

www.acmicpc.net/problem/1818

1818번: 책정리

 

LIS 알고리즘의 응용문제다

 

LIS 는 가장 긴 증가 부분 수열을 찾는 알고리즘으로

수열을 찾을때 이분탐색을 활용하여 찾아야만 O(NlogN) 의 시간 복잡도로 탐색이 가능하다.

 

- 참고 : chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

- C++

#include <iostream>
 
#define MAX 200001
 
using namespace std;
 
int N;
int arr[MAX], lis[MAX];
 
int bs(int left, int right, int target) {
    int mid;
    
    while(left < right) {
        mid = (left + right) / 2;
        
        if (lis[mid] < target) left = mid + 1;
        else right = mid;
    }
    
    return right;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> arr[i];
    
    int j = 0, i = 1; // j 는 lis 의 인덱스, i 는 arr 의 인덱스
    lis[0] = arr[0]; 
    
    while(i < N) {
        if (lis[j] < arr[i]) {
            lis[j + 1] = arr[i];
            j++;
        } else {
            int idx = bs(0, j, arr[i]);
            lis[idx] = arr[i];
        }
        i++;
    }
    
    cout << N - (j + 1);
    
    return 0;
}