[BOJ] 12783. 가장 긴 증가하는 부분 수열 3

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

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

12015번 가장 긴 증가하는 부분 수열 2 문제(문제 링크)와 거의 똑같은 LIS 문제이다. (12015번 문제 풀이 링크)

 

 

 

두 문제의 차이는 수열의 값의 범위뿐이다. 이번 문제에서는 범위가 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 으로 처음에 벡터에 넣어놓는 값으로 -1,000,000,000보다 작은 값을 넣어놓기만 하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
vector<int> vt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vt.push_back(-2000000000);
 
 
 
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num > vt.back()) {
            //벡터의 가장 마지막 값보다 크다면(증가하는 순서) push
            vt.push_back(num);
        }
        else {
            //num이상의 값이 처음으로 나타나는 위치에 num을 넣는다.
            int index = lower_bound(vt.begin(), vt.end(), num) - vt.begin();
            vt[index] = num;
        }
    }
 
 
 
    //처음에 넣어놓은 0을 제외한 벡터의 사이즈가 최장 증가 수열의 길이
    cout << vt.size() - 1 << '\n';
 
    return 0;
}