[코딩테스트] [BOJ11053] 가장 긴 증가하는 부분 수열

문제

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

---

풀이

1. algorithm 헤더의 std::lower_bound로 배열을 순회하며 요소가 value보다 크거나 같을 때, 해당 위치를 value값으로 바꿔준다.

2. 만약 end iterator을 반환하는 경우, 해당 배열에 value보다 작은 요소밖에 없다는 뜻이기에 value를 push_back 해준다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n =0;
    cin >> n;
    
    vector<int> arr(n, 0);
    
    for(int i=0; i<n; i++)
    {
        cin >> arr[i];
    }
    
    vector<int> lis;
    for(int next : arr)
    {
        vector<int>::iterator iter = lower_bound(lis.begin(), lis.end(), next);
        
        if(iter != lis.end())
        {
            *iter = next;
        }
        else
        {
            lis.push_back(next);
        }
    }
    
    cout << lis.size();
    
    return 0;
}