9.7문제: 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 를 출력한다.
예제 입력
3
9 2
1 9 7 4 2 6 3 11 10
8 4
2 1 4 3 6 5 8 7
8 2
5 6 7 8 1 2 3 4
예제 출력
4
1 2 3 11
4
1 3 6 8
4
5 6 7 8
🤔생각
예제 출력에 LIS의 길이 L과 k 번째 LIS를 출력해야 되므로 LIS를 활용해야 된다는 것을 자연스럽게 떠올릴 수 있다. LIS는 증가하는 수열에서 가장 왼쪽에 있는 기준을 설정하고 그 기준에서 가능한 증가 수열의 최대 길이를 cache1에 저장하는 식으로 구한다. 그러면 cache[1]의 값이 4였다면 0번째 요소(LIS함수에서 -1을 처음에 파라미터로 받기위해서 start + 1을 해서 cache1의 인덱스는 1이지만 실제 해당하는 값은 arr[0])부터 시작하는 최대증가수열의 길이가 4라는 뜻이다. cache1[1]은 4이므로 arr[0] 다음에 올 숫자는 기본적 증가속성을 유지해야 되기 때문에 N > 0이고 arr[N] > arr[0]이어야 된다. 그리고 또한 cache1[N - 1] 는 cache1[1] 보다 1만큼 작아야 된다. 이러한 특성을 만족하는 (N - 1) 값들을 각 기준마다 저장하기 위해서 2차원 벡터를 활용했다(행에는 각 기준에 해당하는 값들이고 열에는 조건을 만족하는 N - 1 값들이 들어감). 그리고 사전순 이므로 arr[]값으로 vector요소들을 오름차순으로 정렬해주었다. 이런 vector를 활용해서 추적을 하면은 K번재 사전순인 LIS를 구할 수 있을 것이라고 생각했다. 그리고 시간을 단축하기 위해서 skip을 활용하였다.
😯부족했던 부분
정렬을 하는 부분에서 v[i].size() - 1을 사용했었는데 이때 문제가 발생하였다. vector의 method인 size가 반환하는 값은 unsiged int이고 1은 int인데 이 두수의 뺄셈 결과는 unsigend int이다. 그래서 연산결과가 -1이 되어야 되는데 unsigend int로는 음수를 처리할 수 없다 보니 오류가 발생한거 같다. 처음에는 이런 사실을 모르니 다른 곳에서 문제가 발생한 줄 알고 다른 부분을 유심히 들여다보면서 시간만 날렸었다.
😀코드
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define INF 2147483647LL
typedef long long lld;
using namespace std;
int arr[500], N;
int cache1[501];
lld cache2[501], K, skip;
vector<vector<int>> v(501);
vector<int> ans;
int LIS(int start) {
if (start == N - 1)
return cache1[start + 1] = 1;
int& ret = cache1[start + 1];
if (ret != -1)
return ret;
ret = 1;
for (int next = start + 1; next < N; next++) {
if (start == -1 || arr[start] < arr[next])
ret = max(ret, 1 + LIS(next));
}
return ret;
}
void connect() {
for (int i = 0; i <= N; i++) {
for (int j = i + 1; j <= N; j++)
if (cache1[i] == cache1[j] + 1 && (i == 0 || arr[i - 1] < arr[j - 1]))
v[i].push_back(j);
}
for (int i = 0; i <= N; i++) {
int size = v[i].size();
for (int j = 0; j < size - 1; j++) {
for (int z = 0; z < size - 1; z++)
if (arr[v[i][z] - 1] > arr[v[i][z + 1] - 1]) {
int tmp = v[i][z];
v[i][z] = v[i][z + 1];
v[i][z + 1] = tmp;
}
}
}
}
lld cnt(int idx) {
if (v[idx].size() == 0)
return 1;
lld& ret = cache2[idx];
if (ret != -1)
return ret;
ret = 0;
for (int i = 0; i < v[idx].size(); i++) {
ret += cnt(v[idx][i]);
ret = min(INF, ret);
}
return ret;
}
void Print() {
for (int i = 0; i < ans.size(); i++)
printf("%d ", ans[i]);
printf("\n");
}
void KLIS(int idx, int count, int valLis) {
if (count == valLis) {
Print();
return;
}
int i = 0;
int maxCnt = -1, maxIdx = -1;
while (i < v[idx].size() && skip >= cnt(v[idx][i])) {
skip -= cnt(v[idx][i]);
i++;
}
if (i < v[idx].size()) {
ans.push_back(arr[v[idx][i] - 1]);
KLIS(v[idx][i], count + 1, valLis);
}
else {
ans.push_back(arr[v[idx][i - 1] - 1]);
KLIS(v[idx][i - 1], count + 1, valLis);
}
}
int main(void) {
int C;
int valLis;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> N >> K;
skip = K - 1;
for (int j = 0; j < N; j++)
cin >> arr[j];
ans.clear();
for (int i = 0; i <= N; i++)
v[i].clear();
memset(cache1, -1, sizeof(cache1));
memset(cache2, -1, sizeof(cache2));
valLis = LIS(-1) - 1;
connect();
cout << valLis << endl;
KLIS(0, 0, valLis);
}
return 0;
}👏후기
책과 아이디어는 유사했던거 같다. 하지만 구현에서는 다른 부분이 있었다. 책에서는 c++ STL의 pair를 사용했고 내가 짠 함수들이 조금씩 결합되어 있는 듯한 느낌이 들었다.
