백준 12738 가장 긴 증가하는 부분 수열 3 C++

 

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

12738번: 가장 긴 증가하는 부분 수열 3

가장 긴 증가하는 부분 수열을 DP가 아닌 이분탐색을 활용한 방법입니다. 

 

LIS[i] = 길이 i+1 인 증가하는 부분 수열들 중 가장 큰 값 중 가장 작은 값

이라고 하면, LIS[i] < LIS[i+1] 은 자명합니다.

(가장 작은 값만 저장하게 되므로, LIS의 길이가 i+1로 증가했다는 것은 LIS[i] 보다 큰 값이 존재한다는 뜻)

 

따라서 LIS 는 오름차순 정렬이 되며, 주어진 수열의 각 값 (arr[j]) 를 LIS 에 대해 이분탐색하여

LIS에서 arr[j] 이하의 값 중 가장 작은 첫 번째 값을 찾도록 합니다.

 

그렇게 되면, LIS[i] < arr[j] 라면, LIS[i+1] = arr[j] 가 되므로 LIS의 길이가 최종적으로 가장 긴 증가하는 부분 수열의 길이가 됩니다.

 

코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> vec;
vector<int> lis; 
// lis[i] : 길이 i+1인 LIS의 가장 큰 수 중 가장 작은 값
// 가장 작은 값들로 저장되므로 오름차순 정렬됨됨

void init()
{
    cin >> n;
    vec.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    lis.resize(n);
}

void calc()
{
    int idx = 0;
    for(int i = 0; i < n; i++) {
        int pos = lower_bound(lis.begin(), lis.begin() + idx, vec[i]) - lis.begin();
        lis[pos] = vec[i];
        if(pos == idx) {
            idx++;
        }
    }
    
    cout << idx;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    calc();
    
}