[14003번] 가장 긴 증가하는 부분 수열 5

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘 :: http://www.crocus.co.kr/583

2. 실제 가장 긴 부분 수열 찾아내기

이 문제를 이해하면 [14002번] 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 문제도 가져갈 수 있다.

일단 위의 링크와 같은 설명이지만, 추가 부연해서 설명하자면

일단 이 문제 테스트 데이터 값 자체가 매우 빈약하다. 

따라서 자신이 맞다고 느껴지는 코드이고 AC를 받은 코드여도 다음과 같은 TC를 돌려보자.

4

4 1 2 3

[답 :: 3, 1 2 3]

4

1 3 4 2

[답 :: 3, 1 3 4]

6

4 5 6 1 2 3

[답 :: 3, 1 2 3] (오른쪽 1 2 3은 4 5 6이 될 수 도있고 여러 답이 될 수 있다.

6

4 9 11 5 7 8 

[답 :: 4, 4 5 7 8]

8

1 6 2 5 7 3 5 6

[답 :: 5, 1 2 3 5 6]

9

3 1 2 4 7 5 6 8 10

[답 :: 7, 1 2 4 5 6 8 10]

lis 알고리즘을 알아도 실제로 lis 배열을 구하기 위해서는 다른 생각을 해야 한다.

왜냐면 1 3 4 2라는 배열이 있을 때 lis알고리즘으로 그대로 lis 배열을 출력하면 1 2 4가 나온다.

하지만 실제 lis 배열은 1 3 4여야 하지만,  1 2 4이면 실제 배열이 아니게 된다.

따라서 우리는 ans라는 pair 배열을 새로 만들고 다음과 같이 정의한다.

ans[].first :: pLis 및 pos - 1을 담고있다.(실제 그 값이 들어갈 수 있는 위치)

ans[].second :: arr[pArr]을 담고있다.(실제 해당하는 값)

이것을 이용하여 아래의 알고리즘 원리를 생각해보자.

실제 lis 배열을 구하는 알고리즘을 보자 

예를들면 다음과 같다.

1 6 2 5 7 3 5 6인 경우

ans배열에는 다음과 같이 들어간다.

first ::  0 1 1 2 3 2 3 4

second :: 1 6 2 5 7 3 5 6

이 값을 first를 기준으로 뒤에서 부터 조사해오면

first가 4일때 (6) - > first가 3일때 (5) -> first가 2일때 (3) 

-> first가 1일때 (2) -> first가 0일때(1)이다.

이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.

이 내용을 이용하면 lis 실제 배열을 구현할 수 있게 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <stack>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int arr[1000001];
int lis[1000001];
pii ans[1000001]; // first :: lis가 될 수 있는 위치, second :: 해당하는 값
stack<int> s;
 
int _lower_bound(int start, int end, int target)
{
    int mid;
    
    while (start < end)
    {
        mid = (start + end) / 2;
 
        if (lis[mid] < target)
            start = mid + 1;
 
        else
            end = mid;
    }
 
    return end + 1;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int pLis = 0, pArr = 1;
 
    lis[pLis] = arr[0];
    ans[0].first = 0;
    ans[0].second = arr[0];
 
    while (pArr < n)
    {
        if (lis[pLis] < arr[pArr])
        {
            lis[++pLis] = arr[pArr];
            
            // lis가 될 수 있는 위치정보를 first에 담고
            // 실제 그 값을 second에 담아준다.
            ans[pArr].first = pLis;
            ans[pArr].second = arr[pArr];
        }
 
        else
        {
            int pos = _lower_bound(0, pLis, arr[pArr]);
            lis[pos - 1] = arr[pArr];
 
            // lis가 될 수 있는 위치정보를 first에 담고
            // 실제 그 값을 second에 담아준다.
            ans[pArr].first = pos - 1;
            ans[pArr].second = arr[pArr];
        }
 
        pArr++;
    }
 
    printf("%d\n", pLis + 1);
    
    /* 
        실제 lis 배열을 구하는 알고리즘을 보자 
        예를들면 다음과 같다.
        
        1 6 2 5 7 3 5 6인 경우
        ans배열에는 다음과 같이 들어간다.
    
        first ::  0 1 1 2 3 2 3 4
        second :: 1 6 2 5 7 3 5 6
    
        이 값을 first를 기준으로 뒤에서 부터 조사해오면
        first가 4일때 (6) - > first가 3일때 (5) -> first가 2일때 (3) 
        -> first가 1일때 (2) -> first가 0일때(1)이다.

        이것을 스택에 담아 역출력하면 1,2,3,5,6이라는 실제 배열을 구할 수 있다.
    */
 
    int t = pLis;
 
    for(int i = n-1; i >= 0; i --)
    {
        if (ans[i].first == t)
        {
            s.push(ans[i].second);
            t--;
        }
    }
 
    while (!s.empty())
    {
        printf("%d ", s.top());
        s.pop();
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>