C++ 백준 14003 (가장 긴 증가하는 부분수열5)

백준 14003 (가장 긴 증가하는 부분수열5)

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

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

---

LIS의 길이와 수열을 O(N*logN)안에 해결해야 하는 문제이다.

 

LIS에 대한 기본이해와 O(N^2)의 시간으로 길이와 수열을 찾는 법, 그리고 O(N*logN)의 시간으로 LIS의 길이만을 찾는 방법은 아래에 있으니 반드시 모두 이해하고 이 글을 읽도록 한다.

 

1. LIS의 길이를 O(N^2)으로 구하는 방법 : 여기(링크)

2. LIS의 길이와 수열을 O(N^2)으로 구하는 방법 : 여기(링크)

3. LIS의 길이를 O(N*log(N))으로 구하는 방법 : 여기(링크)

 

설명

---

!다시 한번 말하지만 반드시 위 세개 링크에 있는 설명을 모두 이해하고 와야 이 글을 이해할 수 있다!

 

LIS 수열찾는 것을 O(N^2)에 해결하는 방법을 이해했다는 가정하에 설명한다.

위의 방법에서 dp의 값을 채워넣는 것은 O(N^2)이 걸렸지만, 역방향으로 탐색해 조건을 맞춰가며 LIS의 수열을 구하는 것은 O(N)의 시간이 걸렸다. (여기서 dp[index]는 num[index]를 포함했을 때의 LIS 길이이다.)

이게 무슨말인가 하면, O(N*logN)의 시간으로 LIS의 길이를 구하는 과정에서 dp의 값만 저장해놓을 수 있다면 위 방법에서 썼던 수열을 구하는 방식을 그대로 가져다 쓰면 된다는 소리다.(O(N)이기 때문에)

 

LIS의 길이를 O(N*logN)의 시간복잡도로 푸는 방법을 이해했다면 각 단계에서 index별 dp의 값을 저장하는 것은 매우 쉽다.

dp[index] = vector L에 추가되었을 때 그때의 index이다.

다음 예시를 따라가보며 이해해보자.

 

{8,14, 9, 17, 2, 15, 16}라는 수열이 있다.

이 방식을 O(N*logN)의 시간복잡도로 LIS를 구할때의 방법을 쓴다면 과정은 다음과같다.

 

1. {8,14, 9, 17, 2, 15, 16}

num[index]	8	14	9	17	2	15	16
vector L	8

8은 L에서 index가 1인 곳에 위치가 되었으니 dp[1] = 1이다.

 

2. {8,14, 9, 17, 2, 15, 16}

num[index]	8	14	9	17	2	15	16
vector L	8	14

14는 L에서 index가 2인 곳에 위치가 되었으니 dp[2] = 2이다.

 

3. {8,14, 9, 17, 2, 15, 16}

num[index]	8	14	9	17	2	15	16
vector L	8	9

9는 L에서 index가 2인 곳에 위치가 되었으니 dp[3] = 2이다.

 

여기까지만 해도 이해가 될 것이다.

이전 글에서도 언급을 했었지만 기존 LIS에서 배열을 돌며 최적의 위치를 찾는다는 것은 자신보다 작으면서 DP의 값은 가장 큰 index를 찾는 것이었다. (이유는 알고있어야 한다) L의 역할이 바로 이것이다.

만약 이 말이 이해가 되지 않는다면 여기(링크)의 설명을 다시 읽고 오자.

 

위 과정을 모두 거치고 나면 dp배열은 다음과 같다.

num[index]	8	14	9	17	2	15	16
dp[index]	1	2	2	3	1	3	4

자 이제 dp배열을 알았으니 O(N)의 시간으로 LIS수열을 가지고 오면 된다. 이 부분은 여기(링크)에서 설명 했었으니 넘어가겠다.

 

구현

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int N;
    cin>>N;
    int *num = new int[N];
    int *dp = new int[N];
    int a;
    int idx, dptmp=0;
    vector <int> L;
    stack <int> s;
    vector <int>::iterator p;
    for(int i=0;i<N;i++){
        cin>>a;
        num[i]=a;
        if(L.size()==0) {
            L.push_back(num[i]);
            dp[i]=1;
        }
        else{
            if(L[L.size()-1]<num[i]) {
                L.push_back(num[i]);
                dp[i] = L.size();
            }
            else{
                p = lower_bound(L.begin(),L.end(),num[i]);
                *(p)=num[i];
                dp[i]=p-L.begin()+1;
            }
        }
        if(dp[i]>dptmp) {
            idx = i;
            dptmp = dp[i];
        }
    }
    cout<<L.size();
    s.push(num[idx]);
    for(int i=idx-1;i>=0;i--){
        if(num[i]<num[idx] && dp[i]+1 == dp[idx]){
            idx = i;
            s.push(num[i]);
        }
    }
    cout<<"\n";
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}

이 과정을 이해한다면 무려 플래티넘 5단계 문제를 정확히 이해하고 풀은 것이다!!