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

백준 14002 (가장 긴 증가하는 부분수열4)

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

14002번: 가장 긴 증가하는 부분 수열 4

---

이 문제는 LIS의 길이 뿐만 아니라 LIS수열 중 하나를 출력하는 문제이다.

이 문제를 풀기에 앞서 LIS의 기본특성과 그 길이를 구하는 방법을 알아야 한다.

 

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

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

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

 

이문제는 O(N^2)안에 해결하면 되므로 LIS의 길이또한 O(N^2)로 구하는 방법을 사용한다.

때문에 LIS의 길이를 O(N^2)으로 구하는 방법을 이해해야 하므로 위 링크를 따라 꼭 이해하고 오자.

 

설명

---

LIS의 길이를 구하고나면 DP배열에 각 index에 해당하는 배열원소를 포함했을 때의 LIS길이가 저장되어있다. 

DP배열을 완성시키는 것(LIS의 길이를 찾는 것)에 O(N^2)이 걸렸으므로 역추적해서 LIS의 수열을 뽑아내는 것도 O(N^2)에 구현해보자.

 

아이디어는 간단하다.

DP값이 가장 컸던 index를 저장해놓고 그 index부터 거꾸로 for문을 j라는 인덱스를 통해

만약 dp[index] = dp[j]+1이고, num[index]보다 num[j]가 작다면 index에 j를 저장한 후 stack에 num[j]를 push한다. 그리고 반복하면 된다.

마지막으로 stack에서 하나씩 pop하면 LIS의 배열이 완성된다.

 

코드를 보며 이해해보자.

구현

---

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

int main() {
	int dp[1000];
	int num[1000];
	int n;
	cin >> n;
	int ans = 0;
    stack <int> s;
    int a;
    int idx = 1;
    for(int i=0;i<n;i++){
        cin>>a;
        num[i]=a;
        int tmp=0;
        for(int j=0;j<i;j++){
            if(num[j]<num[i] && dp[j]>tmp) tmp=dp[j];
        }
        dp[i]=tmp+1;
        if(ans<dp[i]){
            ans=dp[i];
            idx=i;
        }
    }
    s.push(num[idx]);
    int curr= idx;
    for(int i=idx-1;i>=0;i--){
        if(num[i]<num[curr] && dp[i]+1==dp[curr]){
            curr=i;
            s.push(num[i]);
        }
    }
    cout<<ans<<"\n";
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
	return 0;
}

대충 짜서 난잡하지만 코드를 따라가보면 이해가 될것이다.

그러나 이 방법은 O(N^2)만큼의 시간이 걸리므로 배열의 크기가 작을때만 사용하도록 하자.