백준 12015 - 가장 긴 증가하는 부분 수열 2

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

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

 

고려사항

• dp를 활용한 lis 알고리즘을 사용하면 정답은 구할 수 있다. ( 백준 11053 문제 글 15 - 23 라인 참조)
• 이러한 2중 for문을 수열의 길이만큼 100만번씩 돌리면 당연히 시간초과.
  자신보다 작으면서, 부분 수열의 길이가 제일 긴 memo값을 찾는 for문을 이분탐색 아니면 세그먼트 트리로 구하면 시간단축가능!
• 그런데 더 간단한 방법을 발견 ( 구글링... )
• lower_bound( begin, end, num) 함수를 활용.
  lower_bound( ) 는 vector 의 원소들 중에서 num보다 크거나 같은 첫 원소의 위치(iter)를 반환한다.
  첫 원소이기 때문에, vector가 정렬되어 있다면, 원소 중 num 과 같은 수를 찾거나 없으면, num보다 큰 수들 중 가장 작은 수를 반환.
  정렬 되어있지 않으면 num과 같은 수의 위치를 반환하거나, 없으면 큰 수들 중 처음으로 만나는 수의 위치를 반환한다.
  위 문제에서는 vector에 담기는 수들이 문제의 조건을 만족하는 수들, 즉! 증가형태를 띄는 수열이기 때문에 이미 정렬되어서 차곡차곡 생성 될 것이다!
• 입력 받은 수가 v.back() 즉, 부분 수열 중 가장 큰값보다 크면, push_back()
• 작다면, lower_bound() 를 통해 num이 들어갈 위치를 찾고, 교체해준다.
• 모든 수를 처리했을 때, vector의 사이즈가 가장 긴 부분 수열 길이이다.
• 단, 벡터에 담겨있는 수열이 옳은 수열이지는 않다! 단지 길이만 알 수 있다.
  예를들어, 수열 [ 10, 20, 30, 15, 40 ] 의 정답 부분 수열은 [ 10, 20, 30, 40 ] 으로 길이가 4이지만,
  위 알고리즘으로 문제를 풀면 [ 10, 20, 30 ] 형태에서 15를 처리해 줄 때,
  lower_bound(15) => 20 위치 반환 => [ 10, 15, 30, 40 ]의 형태로 벡터가 구성된다.
  당연히 15가 30 보다, 뒤에 등장하기에 문제 조건에 맞지 않는다!
• 따라서 위 알고리즘은 단순히 가장 긴 증가하는 부분 수열의 길이만을 알 수 있다! ( 사실 dp를 활용한 lis 알고리즘도 마찬가지다 )

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

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, num;
    vector<int> v(1,1000001);

    cin>>n;
    for(int i=0;i<n;++i){
        cin>>num;
        if(v.back() < num){
            v.push_back(num);
        }else{
            auto iter = lower_bound(v.begin(), v.end(), num);
            *iter = num;
        }
    }

    cout<<v.size();
    return 0;
}