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

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

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

 

 

0. 알고리즘 분류

이분탐색, 가장 긴 증가하는 부분 수열(o(n log n))

 

 

1. 문제

 

 

2. 풀이

11053번: 가장 긴 증가하는 부분 수열 의 연장선 문제다. 단순하게 수의 범위(1000에서 1000000으로)만 증가했다. 코드에서 차이점은, 11053번은 이분 탐색을 직접 구현하여 풀었지만 12015번은 stl의 lower_bound를 사용했다. 오름차순 정렬된 배열에서 어떤 값 이상의 숫자가 처음 나오는 인덱스를 반환하는 함수이다.

 

 

3. 코드

#include <cstdio>
#include <vector>
#include <climits>

using namespace std;

int main() {

    int N, temp, cnt = 0;
    vector <int> v;

    v.push_back(INT_MIN);

    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &temp);
        if (temp > v.back()) { v.push_back(temp); cnt++; }
        else {
            vector<int>::iterator low = lower_bound(v.begin(), v.end(), temp);
            *low = temp;
        }
    }
    
    printf("%d\n", cnt);

    return 0;
}