취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14003번 문제인 가장 긴 증가하는 부분 수열 5이다.
문제는 아래 링크를 확인하자.

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

크기 100만의 수열이 주어질 때, LIS중 하나를 찾아 출력해주면 된다.

LIS중 하나를 역추적하기 위하여 글쓴이는 수를 입력받을 때마다 그 수로 끝나는 가장 긴 증가하는 부분수열의 이전 수가 무엇인지를 기록해두었다. 그리고, LIS를 이루는 마지막 수를 찾아 위의 기록해둔 배열을 이용하여 LIS를 역추적하였다.

(세그먼트트리로 LIS 구하기 연습2)

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> arr;
int seg[2097153];

int nth(int L, int R, int n) {
    int sI = 1;
    while (L < R) {
        if (seg[sI * 2] < n) {
            L = (L + R) / 2 + 1;
            sI = sI * 2 + 1;
        }
        else {
            R = (L + R) / 2;
            sI = sI * 2;
        }
    }
    return L;
}

int update(int L, int R, int qI, int qVal, int sI) {
    if (R < qI || qI < L) return seg[sI];
    if (L == R) return seg[sI] = qVal;
    return seg[sI] = max(update(L, (L + R) / 2, qI, qVal, sI * 2), update((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int rangemax(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 0;
    if (qL <= L && R <= qR) return seg[sI];
    return max(rangemax(L, (L + R) / 2, qL, qR, sI * 2), rangemax((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int inv[1000001];
int val[1000001];
int parent[1000000];
bool xcomp(pair<int, int> p1, pair<int, int> p2) {
    if (p1.first != p2.first) return p1.first < p2.first;
    return p1.second > p2.second;
}

bool icomp(pair<int, int> p1, pair<int, int> p2) {
    return p1.second < p2.second;
}

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

    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        arr.push_back({ x,i });
    }

    sort(arr.begin(), arr.end(), xcomp);

    for (int i = 1; i <= N; i++) {
        val[i] = arr[i - 1].first;
        arr[i - 1].first = i;
    }

    sort(arr.begin(), arr.end(), icomp);

    int cnt = 0, last;
    for (int i = 0; i < N; i++) {
        int x = arr[i].first;
        int temp = rangemax(1, N, 1, x, 1);
        parent[x] = nth(1, N, temp);
        temp++;
        if (temp > cnt) {
            cnt = temp;
            last = x;
        }
        update(1, N, x, temp, 1);
    }

    cout << cnt << '\n';

    vector<int> stk;
    while (cnt--) {
        stk.push_back(last);
        last = parent[last];
    }

    while (!stk.empty()) {
        cout << val[stk.back()] << ' ';
        stk.pop_back();
    }
}