[백준] 14005 가장 긴 증가하는 부분 수열 5 : C++ 풀이

이론 해설

 

https://majesty1317.tistory.com/20

동적 프로그래밍을 통한 LIS O(nlogn)에 구하기

 

upper_bound 를 구하는 함수 구현에 관한 해설

 

https://majesty1317.tistory.com/22

[백준] 12015 가장 긴 증가하는 부분 수열 2 : C++ 풀이

 

코드

#include<iostream>
#include<stack>
using namespace std;

int N, len;
int idx[1000004];
int arr[1000004];
int dp[1000004] = {-1000000001, 0, };

int find_place(int item) {
    int upper_bound = 0;
    int lo = 1, hi = len, mid;
    while(lo <= hi) {
        mid = (lo + hi)/2;
        if(dp[mid] >= item) {
            hi = mid - 1;
            upper_bound = mid;
        }
        else lo = mid + 1;
    }
    
    return upper_bound;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    for(int i=0; i<N; ++i) {
        cin>>arr[i];
        if(dp[len] < arr[i]) {
            ++len;
            dp[len] = arr[i];
            idx[i] = len;
        }
        else {
            idx[i] = find_place(arr[i]);
            dp[idx[i]] = arr[i];
        }
    }
    cout<<len<<'\n';
    int ans_idx = len;
    stack<int> ans;
    for(int i=N-1; i>=0; --i) {
        if(ans_idx == 0) break;
        if(idx[i] == ans_idx) {
            ans.push(arr[i]);
            ans_idx--;
        }
    }
    while(!ans.empty()) {
        cout<<ans.top()<<' ';
        ans.pop();
    }
}