[백준] [C++] 14003번 가장 긴 증가하는 부분 수열 5 (bsearch)

1. 문제

14003번: 가장 긴 증가하는 부분 수열 5 (acmicpc.net)

14003번: 가장 긴 증가하는 부분 수열 5

 

2. N log N 

 

O (N lg N) 만에 lis를 구하는 방법

 

키워드는 "증가"

 

인덱스 0 부터 차례대로 수열의 수들을 스택에 담는다.

 

이때 top보다 더 작은 수가 들어온다는것은 lis가 연결되지 않는다는 의미이다.

 

하지만 이 원소를 포함한 lis가 만들어 질 수 도 있다.

 

따라서 이 원소를 스택안에서 이것보다 크지만 최소인 원소랑 바꾼다 (lower bound)

 

 

3. 추적

 

스택에 원소를 담을때 이어지는 이전 수의 인덱스를 같이 저장하게되면

 

마지막 lis가 완성되고 스택의 top에서부터 같이 저장한 이 인덱스를 따라 올라가면

 

실제 lis를 구할 수 있다.

 

 

4. 코드 1

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
int N;
vector<int> seq;
vector<vector<pair<int, int>>> lls; //first => value, second => idx
 
void insert(int x) {
    int j = -1;
    if(lls.empty() || lls.back().back().first < x) {
        if(!lls.empty()){
            j = lls.back().size() - 1;
        }
        lls.push_back({{x, j}});
    } 
    else {
        int lo = -1, hi = lls.size();
 
        while(true) {
            int mid = (lo + hi)/2;
            if(lo + 1 == hi) {
                if(hi != 0) {
                    j = lls[hi-1].size() -1;
                }
                lls[hi].push_back({x, j});
                break;
            }
            if(lls[mid].back().first < x) {
                lo = mid;
            } 
            else {
                hi = mid;
            }
        }
    }
}
void print(int i, int j) {
    if(i == -1) return;
    print(i - 1, lls[i][j].second);
    cout<<lls[i][j].first<<" ";
}
void solve() {
    for(int i = 0; i < N; i++) {
        insert(seq[i]);
    }
    cout<<lls.size()<<"\n";
    print(lls.size() -1, 0);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    seq = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin>>seq[i];
    }
    solve();
}

 

5. 코드 2

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
int N;
vector<int> seq;
vector<vector<pair<int, int>>> lls; //first => value, second => idx
 
void insert(int x, int idx) {
    if(lls.empty() || lls.back().back().first < x) {
        lls.push_back({{x, idx}});
    } 
    else {
        int lo = -1, hi = lls.size();
 
        while(true) {
            int mid = (lo + hi)/2;
            if(lo + 1 == hi) {
                lls[hi].push_back({x, idx});
                break;
            }
            if(lls[mid].back().first < x) {
                lo = mid;
            } 
            else {
                hi = mid;
            }
        }
    }
}
void print(int idx, int seqIdx) {
    if(idx == -1) return;
    int lo = -1, hi = lls[idx].size();
    while(true) {
        int mid = (lo + hi)/2;
        if(lo + 1 == hi) {
            seqIdx = lls[idx][mid].second;
            break;
        }
        else if(lls[idx][mid].second < seqIdx) {
            lo = mid;
        }
        else {
            hi = mid;
        }
    }
    print(idx -1 , seqIdx);
    cout<<seq[seqIdx]<<" ";
}
void solve() {
    for(int i = 0; i < N; i++) {
        insert(seq[i], i);
    }
    cout<<lls.size()<<"\n";
    print(lls.size() - 1, N - 1);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    seq = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin>>seq[i];
    }
    solve();
}