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

백준

---

🤔문제 이해

LCS(longest common sequence)문제로 11053번과 유사하지만 n과 Ai의 크기가 훨씬 큰 버전의 문제이다.

---

🔥풀이🔥

lower_bound를 이용하면 되는 문제이다.

수열이 저장되어 있는 arr과 가장 긴 부분 수열을 찾아 넣어줄 벡터 v를 선언해주었다

가장 먼저 v에 arr[0] 원소를 넣어주고 arr의 1번째 원소부터 마지막까지 for문을 돌려주었다.

for문에서는 v의 가장 마지막 원소보다 arr[i]번째 원소가 더 큰 경우엔 v.push_back(arr[i])를 해주었다.

그렇지 않은 경우는 v에서 arr[i]보다 크거나 같은 원소 중에서 index가 가장 작은 원소의 iterator를 탐색하고 그 위치에 arr[i]를 넣어주었다. 이 부분이 조금 이해가 안되었는데 아래 예시를 보면 느낌이 올 것이다.

 

예제를 살펴보자

7
10 20 10 30 20 50 25

이 입력으로 주어졌을 때 위 경우대로 한다면 for문에서 i가 5까지 수행한 경우에 v의 상태는

10 20 30 50이 된다.

i가 6일 때 arr[i] = 25이고, v의 마지막 원소는 50이 되는데 이 경우에는 if문을 만족하지 않아 else문으로 들어간다

여기서 iter에는 v[2]인 30에 해당하는 위치가 저장된다.

그 위치에 arr[i]에 해당하는 25가 들어가게 된다.

그렇게 되면 벡터 v에 저장된 원소들은 가장 긴 부분 수열 자체를 의미하지 않게 되는데 v의 size가 왜 답이 되는지 궁금할 것이다. 이때 v의 상태는 

10 20 25 50이 된다.

여기서 25가 30의 위치에 들어간건 30이 있었던 위치에서 25가 20보다는 크고 50보다는 작을 수 있기 때문이다.

30 뒤에 25가 추가된 것이 아니라 30이 있던 자리에 들어간 것이므로 20<x<50의 자리를 대체한 것 뿐이라고 생각하면 된다.

---

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

using namespace std;
int n;
int arr[1000001];
vector<int> v;

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

    cin >> n;

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