BOJ 12015 - 가장 긴 증가하는 부분 수열2(C++)

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

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

풀이

벡터의 초기 상태 {0}

현재 입력 값이 벡터의 마지막 값보다 크면 -> 벡터에 push_back

                                                 작으면 -> lower_bound를 이용해 입력값보다 작거나 큰 위치를 찾아내서 교환

벡터의 초기값 0을 제외해야하기 때문에 v.size() - 1을 출력

ex) {10, 20, 30, 5, 10, 20, 30, 40}

0. {0}

1. 10 마지막 값보다 큼 {0, 10} 

2. 20 마지막 값보다 큼 {0, 10, 20}

3. 30 마지막 값보다 큼 {0, 10, 20, 30}

4. 5 lower_bound  {0, 10, 20, 30} -> {0, 5, 20, 30}

5. 10 lower_bound  {0, 5, 20, 30} -> {0, 5, 10, 30}

6. 20 lower_bound  {0, 5, 10, 30} -> {0, 5, 10, 20}

7. 30 마지막 값보다 큼 {0, 5, 10, 20, 30}

8. 40 마지막 값보다 큼 {0, 5, 10, 20, 30, 40}

* 만약 {10, 20, 30, 5, 10}를 기준으로 5에서 시작하는 증가 부분 수열은 {0, 5, 10}이 되지만 현재까지의 최대 길이 증가 부분 수열은  {0, 5, 10, 30}으로 저장하여 길이를 알 수 있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;
int main() {
    cin >> N;
    vector<int> v;

    vector<int>::iterator iter;
    v.push_back(0);
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        if (temp > v[v.size() - 1])
            v.push_back(temp);
        else {
            iter=lower_bound(v.begin(), v.end(), temp);
            *iter = temp;
        }
    }
    
    cout << v.size() - 1;
    return 0;
}