[C/C++] 백준 - 18892번 : 가장 긴 증가하는 부분 수열 ks

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

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

문제

N개의 정수로 이루어진 수열 A1, A2, ..., AN에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 L이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, K번째 오는 수열을 구해보자.

두 LIS Ai1, Ai2, ..., AiL와 Aj1, Aj2, ..., AjL이 있을 때, ik ≠ jk를 만족하는 k가 하나라도 존재하면 다른 LIS이다.

 

 

종만북의 풀이를 참고하였다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, K;
int cache[503];
int cacheCnt[503];
vector<int> s;

const int MAX = 2000000000 + 1;

void input() {
	cin >> N >> K;
	s = vector<int>(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}
}

int path(int start) {
	int& ret = cache[start + 1];
	if (ret != -1) return ret;
	ret = 1;
	for (int next = start + 1; next < N; ++next) {
		if (start == -1 || s[start] < s[next]) {
			ret = max(ret, path(next) + 1);
		}
	}
	return ret;
}

int count(int start) {
	if (path(start) == 1) return 1;
	int& ret = cacheCnt[start + 1];
	if (ret != -1) return ret;

	ret = 0;
	for (int next = start + 1; next < N; ++next) {
		if ((start == -1 || s[start] < s[next]) && path(start) == path(next) + 1) {
			ret = min<ll>(MAX, (ll)ret + count(next));
		}
	}
	return ret;
}

void reconstruct(int start, int skip, vector<int>& lis) {
	if (start != -1) lis.push_back(s[start]);
	vector<pair<int, int>> followers;
	for (int next = start + 1; next < N; ++next) {
		if ((start == -1 || s[start] < s[next]) && path(start) == path(next) + 1) {
			followers.push_back({ s[next], next }); 
		}
	}
	sort(followers.begin(), followers.end());

	for (int i = 0; i < followers.size(); i++) {
		int index = followers[i].second;
		int cnt = count(index);
		if (cnt < skip) {
			skip -= cnt;
		}
		else {
			reconstruct(index, skip, lis);
			break;
		}
	}
}

void solution() {
	memset(cache, -1, sizeof(cache));
	memset(cacheCnt, -1, sizeof(cacheCnt));

	vector<int> answer;
	reconstruct(-1, K, answer);
	if (answer.size() == 0) {
		cout << -1 << endl;
		return;
	}
	for (auto& t : answer) cout << t << " ";
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}