[Algospot] k번째 최대 증가 부분 수열 (문제 ID : KLIS)

문제

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 _단조 증가_할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 하며, 이 중 가장 긴 것을 최대 증가 부분 수열 (LIS, longest increasing subsequence) 라고 한다. 예를 들어, 5 20 21 22 8 9 10 의 최대 증가 부분 수열은 5 8 9 10 이다.

어떤 수열에는 LIS 가 두 개 이상 있을 수 있다. 예를 들어, 4 5 6 1 2 3 의 LIS 는 두 개가 있다.

모든 숫자가 서로 다른 (중복 숫자가 없는) 수열이 주어질 때, 이 수열의 LIS 중 사전 순서대로 맨 앞에서 k번째 있는 LIS 를 출력하는 프로그램을 작성하시오.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 과 K 가 주어진다. K 는 32비트 부호 있는 정수에 저장할 수 있다. 그 다음 줄에 N개의 정수로 수열이 주어진다. 각 정수는 1 이상 100,000 이하이며, 같은 수는 두 번 등장하지 않는다.

주어진 수열의 LIS 는 최소 K 개 있다고 가정해도 좋다.

 

출력

각 테스트케이스마다 두 줄을 출력한다. 첫 줄에는 LIS 의 길이 L 을 출력하고, 그 다음 줄에 L 개의 정수로 K번째 LIS 를 출력한다.

---

얼마 전에도 풀었던 최대 증가 부분 수열의 활용 문제이다. 다만 단계가 좀 나뉘어있고 할 게 많아서 어려운 문제이다.

일단 lis 함수와 len[] 배열을 통해 가장 긴 증가하는 배열의 길이를 구해야한다. len[i]는 i에서 시작하는 최장 길이를 뜻한다. 

그 후엔 count 함수와 cnt[] 배열로 최대 증가하는 부분 수열의 개수를 구해야한다. 마찬가지로 cnt[i]는 i에서 시작하는 최대 증가 부분 수열의 수이다. 이 두 함수를 이용해 reconstruct해서 수열을 구해낸다. 

 

함수를 하나씩 뜯어보면 lis 함수는 p[start]보다 p[next]가 더 크면 len[start]를 len[start]값과 len[next]+1 중에 더 큰값으로 저장한다. 적어도 배열이 본인을 포함해 한 개는 있기 때문에 1로 초기화 하는것을 유의하자.

그 후 count는 lis를 활용해 구한다. lis(start)가 1이라면 더 증가하는 수열이 없다는 뜻이므로 1을 반환한다. for문 내의 if문에서 볼 조건은 p[start]가 당연히 p[next]보단 작아야한다. 그리고 lis(start)가 lis(next)+1과 같아야 한다. 그래야 최대 증가하는 수열을 만들 수 있기 때문이다. 이 조건을 만족하는 count(next)값을 모두 더해 오버플로가 나지 않도록 min을 취하면 최대 증가하는 부분 수열의 갯수를 구할 수 있다.

 

마지막으로 reconstruct 함수는 좀 까다로웠다. 정답 배열을 저장하는 ans 벡터를 매개변수로 받는다. start가 -1이 아니면 p[start]를 ans벡터에 포함시킨다. 그 후 다음 p[]값과 idx를 저장하는 벡터 followers를 만든다. 이 followers에 p[]값이 크고 lis()값이 1작은 next값과 인덱스를 pair를 이용해 저장한다. pair를 이용해 값을 저장하는 방법은 f.push_back(make_pair(a,b))와 f.push_back({a,b})가 있는데 makr_pair를 쓰다가 귀찮아서 요샌 {a, b}를 쓰는 편이다. 아무튼 조건을 충족하는 모든 next값을 저장하고 sort함수를 통해 순서대로 정렬한다. 

그 다음엔 이제 차례대로 idx에 해당하는 count수를 보고 skip보다 작다면 skip에 cnt값만큼 뺀 후 다음 인덱스를 조사하고 더 크다면 이 인덱스가 정답 배열에 포함된다는 뜻이므로 이 인덱스를 start로 하는 reconstruct를 다시 호출해서 정답 배열을 조사한다.

해설을 쓰고도 잘 이해가 될 지 모르겠지만 lis를 활용하는 문제가 많기때문에 알아두면 좋을 것 같다. 저번 모스 부호 문제에서 사용한 K-1번째 정답을 찾는 알고리즘을 이해하도록 하자.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/KLIS.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int C, N, K;
int p[502]; //원본 배열
int len[502]; //i에서 시작하는 최장 길이를 저장하는 dp 배열
int cnt[502]; //i에서 시작하는 최장 길이 수열의 수를 저장하는 dp 배열 
const int MAX = 2000000000 + 1;
int lis(int start)
{
	int& res = len[start+1];
	if (res != -1) return res;
	res = 1;
	for (int i = start + 1; i < N; i++) {
		if (start == -1 || p[i] > p[start]) {
			res = max(res, lis(i)+1);
		}
	}
	return res;
}
int count(int start)
{
	if (lis(start) == 1) return 1;
	int& res = cnt[start+1];
	if (res != -1) return res;
	res = 0;
	for (int i = start + 1; i < N; i++) {
		if ((start == -1 || p[i] > p[start]) && lis(start) == lis(i) + 1) {
			res = min<long long>(MAX, (long long)res + count(i));
		}
	}
	return res;
}

void reconstruct(int start, int skip, vector<int>& ans)
{
	if (start != -1) ans.push_back(p[start]);
	vector<pair<int, int>> followers;
	for (int i = start + 1; i < N; i++) {
		if ((start == -1 || p[start] < p[i]) && lis(start) == lis(i) + 1)
			followers.push_back({ p[i],i });
	}
	sort(followers.begin(), followers.end());
	for (int i = 0; i < followers.size(); i++) {
		int idx = followers[i].second;
		int cnttmp = count(idx);
		if (cnttmp <= skip)
			skip -= cnttmp;
		else {
			reconstruct(idx, skip, ans);
			break;
		}
	}
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N >> K;
		memset(len, -1, sizeof(len));
		memset(cnt, -1, sizeof(cnt));
		for (int i = 0; i < N; i++) cin >> p[i];
		cout << lis(-1) - 1 << endl;
		vector<int> ans;
		reconstruct(-1, K - 1, ans);
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << " ";
		cout << endl;
	}
}