가장 긴 증가하는 부분 수열(LIS)

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

12015번: 가장 긴 증가하는 부분 수열 2

 

https://velog.io/@junttang/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C

BOJ - 12015 가장 긴 증가하는 부분 수열 2 해결 전략 (C++)

완벽하게 설명을 해놓으셨다.

 

이걸 그냥 set와 lower_bound로 구현만 해주자.

 

<소스 코드>

#include <iostream>
#include <set>
#include <vector>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> arr;
    arr.resize(n + 1);
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
 
    set<int> lis;
    lis.insert(arr[0]);
 
    for (int i = 1; i < n; i++)
    {
        auto iter = lis.rbegin();
        if (*iter > arr[i])
        {
            auto tmp = lis.lower_bound(arr[i]);
            lis.erase(tmp);
            lis.insert(arr[i]);
        }
        else
        {
            lis.insert(arr[i]);
        }
    }
 
    // 출력
    /*for (auto iter = lis.begin(); iter != lis.end(); iter++)
    {
        cout << *iter << ' ';
    }
    cout << '\n';*/
    cout << lis.size() << '\n';
 
    return 0;
}