[백준/BOJ] 18838 가장 긴 증가하는 부분 수열 K (c++)

[백준/BOJ] 18838 가장 긴 증가하는 부분 수열 K (c++)

18838번: 가장 긴 증가하는 부분 수열 k

2025.03.04 - [Competitive Programming] - 14. Longest Increasing Subsequence (LIS, c++)

14. Longest Increasing Subsequence (LIS, c++)

---

이번 문제에서는 LIS의 갯수뿐만 아니라 사전 순으로 적었을 때 K번째 LIS가 어떤 것인지를 찾아야 합니다.

 

2025.03.04 - [문제풀이] - [백준/BOJ] 17411 가장 긴 증가하는 부분 수열 6 (c++)

[백준/BOJ] 17411 가장 긴 증가하는 부분 수열 6 (c++)

위 문제의 접근 방법과 동일한 방식으로 해결할 수 있습니다.

 

{ 2, 1, 5, 0, 7, 4, 8, 3 } 이라는 수열에 대해서 아래와 같은 값이 구해지게 됩니다.

	r	upper_bound	psum (전체 합 - upper_bound index)  = upper_bound 숫자까지의 경우의 수
3	r[1] = { 3 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (0-0)=0, psum[1] = { 0, 0 }
8	r[3] = { 8 }	-	psum[3] = { 0, 1 }
4	r[1] = { 3, 4 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (0-0)=0, psum[1] = { 0, 0, 0 }
7	r[2] = { 7 }	r[3]에 수행 = 0	psum[3]에 대해 수행 (1-0)=1, psum[2] = { 0, 1 }
0	r[0] = { 0 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (0-0)=0, psum[0] = { 0, 0 }
5	r[1] = { 3, 4, 5 }	r[2]에 수행 = 0	psum[2]에 대해 수행 (1-0)=0 psum[1] = { 0, 0, 0, 1 }
1	r[0] = { 0, 1 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (1-0)=0 psum[0] = { 0, 0, 1 }
2	r[1] = { 0, 1, 2 }	r[1]에 수행 = 0	psum[1]에 대해 수행 (1-0)=0 psum[0] = { 0, 0, 1, 2 }

 

이전 문제를 해결한 방식대로라면 r에는 항상 오름차순으로 숫자들이 정렬되어 있으며 계산되어오는 방식에서 psum은 LIS에서 k번째 숫자에 대한 값은 LIS에서 k+1번째 숫자들의 합으로 계산된 값입니다.

 

따라서 가능한 경우의 수를 줄여나가면 K번째 수열을 구할 수 있습니다.

 

LIS의 총 경우의 수는 2개이며 그 2개는 psum[0]을 보면,

r[0] 의 2번째 숫자(1)로 시작하는 1개, 3번째 숫자(2)로 시작하는 1개임을 알 수 있습니다.

 

동일한 방식으로 r[1]에 대해, r[2]..r[LIS_LENGTH]에 대해 K번째 숫자를 탐색할 수 있습니다.

 

K번째 수열을 찾을 때, 해당 위치에서 i번째 수가 K개를 만들 수 있다면 (K개를 포함한다면) i 번째 숫자가 K번째 수열에 포함되는 것이고, K개를 만들 수 없다면 (K보다 작다면) i번째 수로는 불가능 하니 i+1 번째 수에 대해 K-(i번째 수로 만들 수 있는 경우의 수)를 찾아가면 됩니다.

 

단, 이전 문제에서 upper_bound를 찾아서 합을 구한 것과 동일하게 LIS의 이전 숫자보다 큰 경우만을 찾아서 갯수를 세어주면 됩니다.

 

이 문제에서는 경우의 수가 unsigned long long도 초과할 수 있습니다. 따라서 문제에서 제시한 10^18로 경우의 수 상한을 정해두어야 계산이 틀어지지 않습니다.

---

 

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
#define MAX 1000000000000000000

int N, x;
long long K;
vector<int> a, d, p;
vector<vector<int>> r(100000);
vector<vector<long long>> psum(100000);

int solve() {
    REP(i, 0, N) {
        int index = lower_bound(d.begin(), d.end(), a[i])-d.begin();
        if (index >= (int)d.size()) d.push_back(a[i]);
        else d[index] = a[i];
        p.push_back(index);
    }
    REP(i, 0, (int)d.size()) {
        psum[i].push_back(0);
    }
    REP(i, 0, N) {
        int len = p[N-i-1];
        if (len == (int)d.size()-1) {
            long long z = psum[len].back()+1;
            if (z >= MAX) z = MAX;
            psum[len].push_back(z);
        } else {
            int index = upper_bound(r[len+1].begin(), r[len+1].end(), a[N-i-1])-r[len+1].begin();
            long long cnt = psum[len+1].back()-psum[len+1][index];
            long long z = psum[len].back()+cnt;
            if (z >= MAX) z = MAX;
            psum[len].push_back(z);
        }
        r[len].push_back(a[N-i-1]);
    }
    if (psum[0].back() < K) {
        cout << "-1";
        return 0;
    }
    long long k = K;
    vector<int> ans;
    REP(i, 0, (int)d.size()) {
        int start;
        if (i == 0) start = 0;
        else start = upper_bound(r[i].begin(), r[i].end(), ans[i-1])-r[i].begin(); 
        REP(j, start, (int)r[i].size()) {
            long long cnt = psum[i][j+1]-psum[i][j];
            if (cnt == 0) continue;
            if (k <= cnt) {
                ans.push_back(r[i][j]);
                break;
            }
            k -= cnt;
        }
    }
    REP(i, 0, (int)d.size()) {
        cout << ans[i] << " ";
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    solve();
    return 0;
}