KLIS (중상, p. 299)

2025년 11월 2일

어떻게 풀었나?#

LIS(Longest Increasing Subsequence)를 사전순으로 정렬했을 때 K번째 LIS를 구하는 문제.

처음에는 가능한 모든 LIS를 구하고, 그것들을 정렬해서 K번째 LIS를 출력하려고 했다.

당연히 RTE

아무래도 이렇게 풀리면 난이도 ‘상’으로 표시되어있을 것 같진 않고, 대충 생각해보니 K값이 좀 클 수도 있겠다는 생각이 들었다. 그래서 LIS를 tree형태로 나타낸 다음에 각 노드별로 subtree의 노드 개수를 counting하고, 그걸로 K번째 수를 찾으려 했다.

기본적인 Tree DP구나 하면서 풀었는데 계속 시간초과, 컴파일실패, 오답을 받게 됐다.

그러다 K값이 32bit 정수범위라는걸 보고 노드별 subtree의 노드 개수가 long long을 넘을 수도 있겠다고 생각하고 이와 관련된 type을 long long으로 바꾸니 드디어 AC가 떴다.

약 2시간동안 진행된 고통의 흔적 😢

문제#

정답 코드#

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v;
vector<vector<int>> storage;
unordered_map<int, vector<int>> tree, ntree;
unordered_map<int, ll> cnt;
unordered_map<int, bool> chk;
vector<int> ans;
ll LIM = (1LL<<33);
ll CntDfs(int x) {
    if(tree[x].empty()) {
        int m = v.size()-1;
        auto it = lower_bound(storage[m].rbegin(), storage[m].rend(), x);
        if(it != storage[m].rend() && x==*it) {
            return cnt[x] = 1;
        }
        else return cnt[x] = 0;
    }
    if(chk[x]) return cnt[x];
    chk[x]=true;
    for(int i = tree[x].size() - 1; i >= 0; i--) {
        int y = tree[x][i];
        ll res = CntDfs(y);
        if(res) {
            cnt[x] += res;
            ntree[x].push_back(y);
        }
        if(cnt[x]>=LIM) cnt[x]=LIM;
    }
    return cnt[x];
}
bool FindDfs(int x, ll k) {
    if(ntree[x].empty() && k == 1) {
        return true;
    }
    for(int i=0; i<ntree[x].size(); i++) {
        int y = ntree[x][i];
        if(cnt[y] < k)
            k -= cnt[y];
        else {
            if(FindDfs(y, k)) {
                ans.push_back(y);
                return true;
            }
        }
    }
    return false;
}
void Init(int n) {
    v.clear();
    storage.clear();
    storage.resize(n, vector<int>());
    tree.clear();
    ntree.clear();
}
void GetTree(int m, int x) {
    for(int i = storage[m].size() - 1; i >= 0; i--) {
        int y = storage[m][i];
        if(y >= x) break;
        tree[y].push_back(x);
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; 
        ll k; 
        cin >> n >> k;
        Init(n);
        // storage[d] = tree의 깊이 [d]에 해당하는 정점들이 list형태로 저장되어있는데, 이 list는
        // 별도로 정렬하지 않아도 항상 내림차순으로 값이 들어가 정렬된 상태를 유지한다.
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if(v.empty()) {
                tree[0].push_back(x);
                v.push_back(x);
                storage[v.size() - 1].push_back(x);
            } else {
                auto it = lower_bound(v.begin(), v.end(), x);

                if(it == v.end()) {
                    int m = v.size() - 1;
                    GetTree(m, x);
                    v.push_back(x);
                    storage[v.size() - 1].push_back(x);
                } else {
                    if(it == v.begin()) {
                        tree[0].push_back(x);
                    } else {
                        int m = it - v.begin() - 1;
                        GetTree(m, x);
                    }
                    *it = x;
                    storage[it - v.begin()].push_back(x);
                }
            }
        }

        ans.clear();
        cnt.clear();
        chk.clear();
        CntDfs(0);
        FindDfs(0, k);
        printf("%lu\n", ans.size());
        reverse(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); i++) {
            printf("%d ", ans[i]);
        }
        puts("");
    }
    return 0;
}