[LIS] BOJ 14002 가장 긴 증가하는 부분 수열 4

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

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

문제 해결 알고리즘

 

1. 배열(v)과, 수열 저장 배열(dp)를 선언한다.

 

2. 수열 저장 배열(dp)에 처음(first)에는 처음부터의 가장 긴 증가하는 부분 수열의 원소 개수를 저장하고, 두 번째(second)에는 바로 전의 원소의 인덱스를 저장하도록 설정한다.

 

수열의 전에 아무 원소도 없는 원소에는 second에 -1을 넣는다.

 

1. v[i]가 v[j]보다 크고, dp[i].first가 dp[j].first + 1보다 작으면, dp[i].first를 dp[j].first + 1로, dp[i].second는 j로 갱신한다.

2. 원래 result값보다 큰값이 들어오면 max_idx와 result 값을 갱신해준다.

 

 

3. 가장 긴 증가하는 부분 수열의 길이(result)를 출력한다.

 

4. 가장 긴 증가하는 부분 수열에서의 가장 큰 원소의 자리(max_idx)에서부터 바로 전 인덱스를 타고 계속 스택(s)에 저장한 후에 스택에 있는 모든 원소들을 출력해준다.

 

1. second가 -1이 될 때까지 계속해서 max_idx에 대한 배열(v)의 값을 스택에 저장해주고, max_idx의 값을 다음 idx로 바꿔준다.

2. 제일 처음 노드는 second의 값이 -1이어서 스택(s)에 들어가지 못했기 때문에 따로 max_idx를 통해 출력해준다.

3. 스택에 있는 모든 원소들을 순서대로 출력해준다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    int num; cin >> num;
    vector<int> v(num);
    vector<pair<int,int>> dp(num);
    int result = 1, max_idx = 0;
    for(int i=0;i<num;i++) cin >> v[i];

    dp[0] = {1,-1};

    for(int i=1;i<num;i++){
        dp[i] = {1,-1};
         for(int j=0;j<i;j++){    
            if(v[i] > v[j] && dp[j].first + 1 > dp[i].first) {
                dp[i].first = dp[j].first + 1;
                dp[i].second = j;
            }
        }
        if(result < dp[i].first) max_idx = i;
        result = max(result, dp[i].first);
    }

    cout << result << '\n';

    stack<int> s;
    while(dp[max_idx].second != -1){
        s.push(v[max_idx]);
        max_idx = dp[max_idx].second;
    } 
    
    cout << v[max_idx] << ' ';

    while(!s.empty()){
        cout << s.top() << ' ';
        s.pop();
    }
}