[BOJ-12738]가장 긴 증가하는 부분수열3

이 문제도 동일하게 lower_bound를 사용하면 풀 수 있는 문제이다.

이전에 풀었던 코드에서 쓸 데 없이 입력을 따로 저장하고 lower_bound를 했었는데 

생각해보니 필요가 없었다. 괜히 메모리만 더 차지하는 꼴이라 입력받으며 lower_bound를 하면 

메모리를 줄일 수 있었다.

3달전에 그렇게 풀었었구나...

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> v;
int main(){
    scanf("%d", &n);
    int input = 0;
    int count = 0;
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &input);
        auto index = lower_bound(v.begin(),v.end(),input);
        if(index == v.end()){
            count++;
            v.push_back(input);
        }else if(index < v.end()){
            *index = input;
        }
    }
    printf("%d\n",count);
    return 0;
}