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

이 문제는 단순히 생각해보면, 스택을 이용해 풀 수 있을 것 같다.
monotone-stack을 이용하면 손쉽게 증가하는 부분 수열을 구해낼 수 있기 때문이다.

하지만, 이렇게 구한 수열이 항상 가장 긴 증가하는 부분수열(LIS)를 보장하지는 못한다.

당장 문제에서 주어진 예시만 하더라도 스택에는 10, 20이 담긴 후, 10이 들어오면 다 비우고 10을 넣은 다음, 30이 들어오면 10, 30을 저장하게 되고, 20이 들어오면 30을 빼고 10, 20을 저장한 뒤, 마지막 값인 50이 들어왔을 때 10, 20, 50을 저장하게 된다.

그래서, 단순히 스택만으로는 풀 수 없는 문제이다.

다음으로는, dp를 생각할 수 있다. i번째까지의 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 저장한다면, dp[i] = dp[j] + 1가 된다.
(단, j < i이며, a[i]보다 작은 원소들 중 dp값이 최대인 인덱스를 의미)
하지만, 이는 시간복잡도가 O(N^2)이므로 시간 초과가 된다.

문제점은 dp[j]를 찾으려면 O(N)이 걸려서 문제인 것이다.

하지만, i번째까지의 부분 수열에서 a[i]는 몇 번째인지 알아내는 것은 이분 탐색을 통해 가능하다.

우리는 부분 수열의 길이가 중요한 것이지 부분 수열에 어떤 값이 들어있는지는 중요하지 않다.

따라서, lower_bound로 원소를 삽입할 위치를 찾고, 그 위치에 원소를 저장해주면 된다.
기존에 해당 인덱스에 원소가 있었다면 대치(replace)될 것이며, 없었다면 삽입(insert)될 것이다.

먼저, lower_bound의 특성상 원소가 삽입될 위치는 항상 맨 마지막이 될 것이다.
이는 i번째까지의 원소들 중 최대값을 찾아내어 lis배열 마지막에 추가했고, 이는 실제 LIS가 길어짐을 의미한다.

그리고, 원소가 대치된다는 것의 의미는 다른 LIS가 만들어질 가능성이 있음을 의미한다.

예를 들어, 10, 20, 5, 30, 10, 20, 50이 입력으로 들어온다고 가정하자.
이때, 배열 lis에 원소들을 lower_bound로 알아낸 인덱스에 저장하는 상황에서 lis배열의 변화를 살펴보자.
1. 10
2. 10, 20
3. 5, 20
4. 5, 20, 30
5. 5, 10, 30
6. 5, 10, 20
7. 5, 10, 20, 50

우리는 위 과정을 통해, 원소가 대치되다가 결국 새로운 LIS가 됨을 확인할 수 있다.

lower_bound로 인덱스를 알아내서 해당 위치의 값을 변경함으로써, lis배열 내에 새로운 LIS가 만들어간다.

그러다가, 기존의 LIS와 길이가 동일해지면, lis배열에는 새로운 LIS가 저장된다는 것을 의미한다.
즉, 기존의 LIS에서 새로운 LIS로 완전히 대치되는 것이다.

따라서, lower_bound로 알아낸 삽입가능한 인덱스에 a[i]를 저장해가면 결국 lis의 길이가 LIS의 길이가 됨을 확인할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n, sz;
int a[1'000'000], lis[1'000'000];

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++) {
        int idx = lower_bound(lis, lis + sz, a[i]) - lis;
        lis[idx] = a[i];
        sz = max(sz, idx + 1);
    }
    cout << sz;
}