[알고스팟] k번째 최대 증가 부분 수열

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • KLIS
  • 2000ms
  • 65536kb
  • 2297
  • 484 (21%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

어떤 정수 수열에서 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 문제입니다! 이전에 비슷하게 푼 문제가 있기 때문에, 해당 문제와 유사하게 풀면 됩니다!

그리고 k 번째의 값을 구해야 하기 때문에 각각의 경우에서 경우의 수가 몇 가지가 나오는지 알아야 한다는 것을 기억합시다! 

해당 문제를 해결하기 위해서는 크게 2 개의 중요한 부분으로 나눌 수 있습니다.

첫 번째는, 각 인덱스마다 LIS의 길이를 구할 것!

두 번째는, 각 인덱스마다 뒤에 나오는 경우의 수가 몇 개 인지 알아 낼 것!

그리고 첫 번째를 구하면서, 각 인덱스마다 LIS를 위해 와야하는 다음 인덱스의 번호를 알 수 있습니다.

그림으로 확인해 보겠습니다!

 

처음에 7을 방문했을 때 7의 LIS가 4라고 합시다! 7에서 이어지는 LIS의 경우의 수는 2 가지 였습니다!

그럼 3의 LIS 길이를 5로 최신화하고, 3에서 이어질 수 있는 경우의 수는 2개가 됩니다.

3에서 LIS를 위해서 7을 방문해야 한다는 정보도 넣읍시다!

2의 경우에는 3보다 작으니 PASS.

8의 경우에는 LIS가 7보다 짧은 3이 나왔습니다!

LIS가 안되는군요! 무시합니다.

아닛! 6을 봤더니 LIS가 5가 나왔습니다!

그렇다면 3에서는 LIS가 6이 될 수 있을 것입니다!

경우의 수도 1로 최신화 해야하고, LIS를 만들기 위한 인덱스들을 저장하는 배열도 바꿔야겠죠!

이렇게 바뀌었습니다! 7은 버려야겠죠.

이제 5를 한번 봅시다. 또 다른 LIS를 만들 수 있는 인덱스를 발견했습니다!

그러면, LIS를 위한 인덱스를 추가하고,  경우의 수도 1 + 2 해서 3으로 만들어 줍시다!

마지막에는 사전순서로 해야하기 때문에 정렬을 해줍니다.

참고로, 이전에 구했던 LIS 길이나 경우의 수들은 모두 저장되어 있는 상태라고 합시다!

그럼 결과는 어떻게 구할까요?!

모스 부호 사전때와 비슷합니다.

만약 현재 인덱스에서 k 번째 LIS를 찾아야 한다면, 다음으로 갈 수 있는 인덱스를 저장한 배열을 돌면서 해당 인덱스에서 만들 수 있는 경우의 수들과 비교 하면서 어떤 인덱스를 선택할지 정합니다.

1) 경우의 수가 k보다 작은 경우 : 스킵 ( k - 경우의 수) 후 다음 인덱스 확인

2) 경우의 수가 k보다 큰 경우 : 해당 경로로 가야 k번째 LIS가 존재한다!

또 그림 예시를 통해 확인해보겠습니다.

자 3번에서 2 번째 LIS를 찾으려고 합니다! 

5 번은 경우의 수가 1개 입니다.

따라서, 5번에서는 2 번째 LIS가 나올 수 없고, 스킵이 가능합니다.

그리고 5 번에서 1개를 스킵했다는 것은 곧 6 번에서 1 번째 LIS를 찾으라는 것과 같은 의미입니다!

따라서 답은 3-6-7-8이 되겠죠!

원래는 6번 에서도 이런 과정을 재귀적으로 진행할 것 입니다.

그렇다면 이를 코드로는 어떻게 작성할까요!?

코드

#pragma once
#include<cstdio>
#include<cstring>
 
long long k;
//lis[x][y] : x에서 LIS를 위해서 방문해야하는 인덱스
// lisLen : x에서 LIS를 위해서 방문해야하는 인덱스의 개수
int lis[501][501], arr[501], lisLen[501];
//len : LIS의 길이, nums : 인덱스에서 만들어질 수 있는 경우의 수
int len[501], n; long long nums[501];
 
//오버플로우 방지
long long mod = 100000000000;
 
struct INFO
{
    int len;
    long long nums;
};
 
long long min(long long i1, long long i2)
{
    return i1 < i2 ? i1 : i2;
}
 
INFO getLIS(int idx)
{
    if (len[idx] != -1) return { len[idx], nums[idx] };
 
    INFO ret;
 
    len[idx] = 1;
    nums[idx] = 1;
 
    for (int i = idx + 1; i <= n; i++)
    {
        if (arr[idx] < arr[i])
        {
            ret = getLIS(i);
 
            //LIS 길이가 최신화 된 경우 전에 들어있던 인덱스를 모두 제거하고 길이를 1로 변경
            //가능한 경우의 수 최신화
            if (ret.len + 1> len[idx])
            {
                len[idx] = ret.len + 1;
                nums[idx] = ret.nums;
                lis[idx][0] = i;
                lisLen[idx] = 1;
            }
            //LIS 길이가 똑같은 경우 인덱스를 목록에 넣고 경우의 수 증가
            else if (ret.len + 1 == len[idx])
            {
                //오버 플로우 방지
                nums[idx] = min(nums[idx] + ret.nums, mod);
                
                //해당 인덱스를 lis목록에 넣고 길이 증가
                lis[idx][lisLen[idx]++] = i;
            }
        }
    }
 
    return { len[idx], nums[idx] };
}
 
int temp[500];
 
//정렬, lis에는 인덱스가 들어있으므로, arr[index]를 기준으로 정렬해야 한다!
void merge(int *a, int left, int m, int right)
{
    int l = left, r = m + 1, k = left;
    
    while (l <= m && r <= right)
    {
        if (arr[a[l]] < arr[a[r]])
        {
            temp[k++] = a[l++];
        }
        else
        {
            temp[k++] = a[r++];
        }
    }
 
    while (l <= m) temp[k++] = a[l++];
    while (r <= right) temp[k++] = a[r++];
 
    for (int i = left; i <= right; i++)
    {
        a[i] = temp[i];
    }
}
 
void mergeSort(int *arr, int left, int right)
{
    if (left < right)
    {
        int m = (left + right) / 2;
 
        mergeSort(arr, left, m);
        mergeSort(arr, m + 1, right);
        merge(arr, left, m, right);
    }
}
 
int res[500], rLen = 0;
 
// nums보다 cnt가 큰 경우 : 해당 nums 만큼 스킵가능
// nums보다 작거나 같은 경우 : 해당 인덱스 안에 cnt 번째 답이 있다!
void setRes(int idx, long long cnt)
{
    for (int j = 0; j < lisLen[idx]; j++)
    {
        if (cnt > nums[lis[idx][j]])
        {
            cnt -= nums[lis[idx][j]];
        }
        else
        {
            res[rLen++] = arr[lis[idx][j]];
            setRes(lis[idx][j], cnt);
            return;
        }
    }
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
 
    while (t--)
    {
        scanf("%d %lld\n", &n, &k);
 
        memset(lisLen, 0, sizeof(lisLen));
        memset(len, -1, sizeof(len));
        rLen = 0;
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%d \n", &arr[i]);
        }
 
        INFO r = getLIS(0);
        r.len--;
 
        for (int i = 0; i <= n; i++)
        {
            mergeSort(lis[i], 0, lisLen[i]-1);
        }
        
        setRes(0, k);
 
        printf("%d\n", r.len);
        for(int i = 0; i < r.len; i++)
            printf("%d ", res[i]);
 
        printf("\n");
    }
 
    return 0;
}
 
 

여담

생각보다 어려웠습니다!

정렬도 구현해줘야 했고,

재귀 함수에서 경우의 수도 반환해야 했기 때문에 구조체를 통해서 2개의 값을 반환하도록 했습니다!

시간복잡도는 LIS의 부분 문제가 n개이고, 부분 문제를 n번 반복해서 풀기 때문에 

입니다. 참고로, 정렬은 병합 정렬이기 때문에 따로 의 시간복잡도를 가집니다.

다만, 이 더 최악의 경우이기 때문에 역시 시간복잡도는 이죠!