BOJ 18892 가장 긴 증가하는 부분 수열 ks

BOJ 18892 가장 긴 증가하는 부분 수열 ks

[분류 : 다이나믹 프로그래밍]

 

[풀이]
  [시작과 끝] 시작과 끝점이 K에 따라 달라질 수 있다. 모든 경우를 생각하기 귀찮으니 시작과 끝을 고정시키기 위해서 0번째에 충분히 작은 값(-10^9)을, N+1번째엔 충분히 큰 값(10^9)을 넣어주고 LIS를 구하자. 배열 A중에 0번째보다 작거나 N+1번째보다 큰 값은 존재할 수 없기 때문에 이 상태로 LIS를 돌려도 똑같은 답을 구해낼 수 있다.

  [추적] 0번째부터 시작해서 K번째 LIS를 찾아간다. 대신 사전순으로 처리해야하기 때문에 갈 수 있는 인덱스 구간을 정렬해주자. set을 이용하면 삭제도 편하고 정렬도 알아서 해주니 편하다.
정렬된 데이터에 대해 i번째에 접근했다고 하자. 그러면 세 가지 경우의 수밖에 없다.

1. i번째를 LIS에 넣으면 K번째보다 작은 것만 가져올 수 있다.
2. i번째를 LIS에 넣으면 K번째가 포함되어 있다.
3. i번째를 LIS에 넣으면 K번째를 초과하게 된다.

  우리가 원하는 것은 2.이므로 이것만 골라서 추적해주고 답에 넣어주면 된다. K에서 (1)을 빼주면서 검사를 진행하면 되시겠다.

 

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int MAX_N = 502, INF = 1e9 + 5;
int N, A[MAX_N], dp[MAX_N], dp2[MAX_N], L;
vector<int> ans;
int rec(int p) {
    if (p == N) return 1;
    int& ret = dp2[p];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = p + 1; i <= N; i++) if (A[p] < A[i] && dp[p] + 1 == dp[i])
        ret = min(INF, ret + rec(i));
    return ret;
}
bool f(int p, int K, set<pair<int, int>>& s) {
    if (p == N) return 1;
    if (p)
        ans.push_back(A[p]);
    int i;
    for (auto& x : s) {
        i = x.second;
        if (A[p] < A[i] && dp[p] + 1 == dp[i]) {
            if (K < rec(i)) {
                for (auto jt = s.begin(); jt != s.end();) {
                    if (jt->second <= i)
                        jt = s.erase(jt);
                    else jt++;
                }
                return f(i, K, s);
            }
            K -= rec(i);
        }
    }
    return 0;
}
int main() {
    memset(dp2, -1, sizeof dp2);
    int i, j, K;
    set<pair<int, int>> s;
    scanf("%d%d", &N, &K);
    dp[0] = 1, A[0] = -INF;
    for (i = 1; i <= N; i++) {
        scanf("%d", &A[i]);
        dp[i] = 1;
        for (j = 0; j < i; j++) if (A[j] < A[i])
            dp[i] = max(dp[i], dp[j] + 1);
        L = max(L, dp[i]);
        s.insert({ A[i], i });
    }
    N++; L++;
    dp[N] = L, A[N] = INF;
    s.insert({ A[N], N });
    if (f(0, K - 1, s))
        for (int& a : ans) printf("%d ", a);
    else puts("-1");
    return 0;
}