백준 3745번 오름세 - C++ 풀이

---

 

1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다.

 

1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다.

 가장 긴 증가하는 부분 수열을 구하는 문제이다. n = 10^5이므로 O(n^2)이 아닌 O(nlogn)의 알고리즘을 사용해서 구해야 한다.

 

반응형

---

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

using namespace std;

int LIS(const vector<int>& arr) {
    vector<int> lis;
    
    lis.push_back(0);
    for (auto x: arr) {
        if (x > lis.back()) {
            lis.push_back(x);
        }
        else {
            int lb = lower_bound(lis.begin(), lis.end(), x) - lis.begin();
            lis[lb] = x;
        }
    }
    
    return lis.size() - 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    
    while (cin >> N) {
        vector<int> v;
        
        for (int i=0; i<N; i++) {
            int x; cin >> x;
            v.push_back(x);
        }
        
        cout << LIS(v) << "\n";
    }

    return 0;
}