백준 14003번 가장 긴 증가하는 부분 수열 5

백준 14003번: 가장 긴 증가하는 부분 수열 5

아이디어

O(NlogN) LIS를 구현하는 방법은 이전에 알아봤다. 길이 i를 만드는 수열의 최소 마지막 숫자를 v[i]에 저장한다. 그럼 이제 그 수열을 어떻게 출력하는게 좋을까? 그냥 v에 저장된거 순서대로 출력하면 당연히 틀린다. 10 20 30 11이 주어지면 11 20 30이 출력될 것이다.

v[i]가 갱신될때마다 이전 값을 기록하면 그걸 계속 따라가면서 증가 부분 수열을 출력할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1000001];
int arr2[1000001]; // 증가 부분 수열에서 이전 값의 인덱스
vector<int> v; // 값
vector<int> v2; // 자기 인덱스

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    v.push_back(-1000000001);
    v2.push_back(-1);

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        auto iter = lower_bound(v.begin(), v.end(), arr[i]);
        if (iter == v.end()) {
            v.push_back(arr[i]);
            v2.push_back(i);
            arr2[i] = *(v2.end()-2);
        }
        else {
            *iter = arr[i];
            v2[iter-v.begin()] = i;
            arr2[i] = v2[iter-v.begin()-1];
        }
    }

    cout << v.size()-1 << '\n';

    vector<int> v3;
    int idx = *(v2.end()-1);
    while (idx != -1) {
        v3.push_back(arr[idx]);
        idx = arr2[idx];
    }

    for (auto iter = v3.rbegin(); iter != v3.rend(); iter++) {
        cout << *iter <<' ';
    }

    return 0;
}

여담

얘도 탑다운으로 풀라면 개어려움. 이거 풀었더니 백준 플레티넘이 되었다. 9월부터 다시 시작했으니까 골드에서 두세달정도 걸린듯? 근데 아직 전역할라면 1년남음 아 ㅋㅋ