[C++][백준 12015] 가장 긴 증가하는 부분 수열 2

[문제]

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

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

[문제 풀이]

가장 긴 증가하는 부분 수열 문제와 달리 단순히 dp 로 풀면 100만 X 100만 이 되기 때문에 시간 초과가 날 수밖에 없는 문제다.

해당 문제를 해결하기 위해서는 그래서 입력 부분에서 애초에 들어갈때 알고리즘적인 로직을 만들어줘야한다.

 

가장 긴 증가하는 부분 수열 문제에 lower bound를 접목시키자.

만약 10 20 30 25 50 60 이라는 배열이 있다고 치면

순서대로 10 20 30 이 들어갔다가 25라는 20보다는 크고 30보다는 작은 숫자가 나올시 30의 위치를 대체해서 25를 넣게 만들어주자.

그러면 결과적으로 10 20 25 50 60이라는 크기가 5인 벡터가 만들어 질 것이다.

또한, lower bound를 사용하면 이분 탐색이라 log N 으로 해결이 가능하므로 해당 문제를 N log N 으로 답을 낼 수가 있다.

 

만일 사이즈가 0이거나 가장 마지막 원소보다 입력값이 크다면 가장 뒤에 추가로 넣어주자.(15~16)

만일 그게 아니라면 해당 원소의 lower bound 를 찾아서 해당 원소를 입력값으로 바꿔주자.(19)(만일 중간값이 바뀐다고 치더라도 우리는 벡터의 사이즈로 답을 찾을 것이기 때문에 뒷쪽의 모든 입력값이 바뀌기 전까지 결과값이 바뀌지가 않는다.)

해당 벡터의 사이즈가 곧 답이다.(22)

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> augment;
    for(int i = 0;i<n;i++){
        int temp;
        cin>>temp;
        if(i == 0 or augment.back()<temp){
            augment.push_back(temp);
        }
        else{
            *lower_bound(augment.begin(),augment.end(),temp) = temp;
        }
    }
    cout<<augment.size()<<endl;
    return 0;
}