[C++] K-th Longest Increasing Sequence KLIS

https://www.algospot.com/judge/problem/read/KLIS

algospot.com :: KLIS

소요 시간: 2시간 26분

해결: X

 

하나의 수열에 대해 여러 LIS가 있을 수 있습니다.

그 중에서 사전순으로 k번째 LIS를 찾는 문제입니다.

---

LIS의 길이를 구하는 방법에 대해서는 좋은 설명이 많이 있으니 생략하겠습니다.

 

LIS의 길이가 있다면 부분 수열에서 구할 수 있는 LIS의 개수도 구할 수 있습니다.

LIS의 개수를 구하는 함수는 길이를 구하는 것과 똑같이 count(start)이고,

수열 S의 start 위치에서 시작하는 LIS 길이의 최적해의 개수를 count 배열에 저장합니다.

이때 k의 값이 32비트 정수 이내로 표현된다는 점만 주의해서 처리해줍시다.

 

최종 문제는 LIS의 길이와, LIS의 개수를 가지고 k번째 LIS를 복원하는 건데요.

LIS의 길이는 다음 원소를 결정하는데 사용하고,

LIS의 개수는 미리 계산할 양을 파악하고 문제를 건너뛰는데 사용하면 되겠네요.

 

첫번째 예제의 정보들을 표에다 정리해봤습니다.

S는 수열, length는 i에서 시작하는 LIS의 길이, count는 i에서 시작하는 LIS의 개수입니다.

i	0	1	2	3	4	5	6	7	8
S[i]	1	9	7	4	2	6	3	11	10
length[i]	4	2	2	3	3	2	2	1	1
count[i]	6	2	2	2	4	2	2	1	1

다음 원소를 선택할 때는 단조 증가를 만족하기 위해 S[i]가 현재보다 커야구요, length[i]가 현재보다 1 작아야 합니다(현재 원소를 제외한 길이).

 

첫번째 원소는 length가 가장 큰 S[0]입니다.

length가 4인 원소가 하나 밖에 없으니 모든 전체 LIS는 S[0]으로 시작하겠지요.

 

두번째 원소는 length가 4보다 1 작은 3이어야 합니다.

length가 3이고 현재 원소보다 큰 S[i]는 S[3]와 S[4]가 있습니다.

이중에서 count와 비교해서 k 이전의 LIS들을 건너뛰면 됩니다.

 

문제에서 조건은 사전순이라 했습니다.

따라서 값이 더 작은 S[4]를 S[3]보다 먼저 고려해야 합니다.

k가 4(count[3])보다 작다면 두번째 원소가 S[4], 크거나 같다면 두번째 원소가 S[3]입니다.

 

이제 재귀로 나머지 문제를 해결하면 됩니다.

각 함수의 구현은 어렵지 않지만 문제 전체의 구조를 생각해내는게 쉽지 않은 거 같습니다.

---

코드

reconstruct의 시간 복잡도는 가장 큰 연산인 정렬(O(nlgn))과 부분 문제 개수(n개)에 의해 O((n^2)lgn)입니다.

const int INF = numeric_limits<int>::max();
const int SZ = 501;
int n, k;
int S[SZ];

int lis_length[SZ];
int calc_length(int start){
    int& ret = lis_length[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(1+calc_length(next), ret);
    return ret;
}

// start 원소에서 시작하는 LIS의 개수
int lis_count[SZ];
int calc_count(int start){
    if(calc_length(start)==1)return 1;
    
    int& ret = lis_count[start+1];
    if(ret!=-1)return ret;
    
    ret = 0;
    for(int next=start+1; next<n; next++){
        // 다음에 올 수 있는 원소의 조건
        // 조건1: 현재 원소보다 커야 함.
        // 조건2: 다음 LIS 길이가 현재 LIS보다 1 작아야 함.
        if((start==-1 || S[start]<S[next])
            && calc_length(start) == calc_length(next)+1)
            // k의 최대값 처리
            ret = min((long long)ret + calc_count(next), (long long)INF);
    }
    return ret;
}

void reconstruct(int start, vector<int>& lis){
    if(start!=-1)lis.push_back(S[start]);
    
    // 다음에 올 수 있는 원소들의 목록
    vector<pair<int,int>> next_list;
    for(int next=start+1; next<n; next++){
        if(calc_length(start)==calc_length(next)+1
        && (start==-1 || S[start]<S[next]))
            next_list.push_back({S[next], next});
    }
    // 사전 순으로 정렬
    sort(next_list.begin(), next_list.end());
    
    for(int i=0; i<next_list.size(); i++){
        int next = next_list[i].second;
        if(k<calc_count(next)){
            reconstruct(next, lis);
            return;
        }
        else k-=calc_count(next);
    }
}