[DP] 11053. 가장 긴 증가하는 부분 수열 4

 

문제

수열 A가 주어졌을 때 가장 긴 증가하는 부분수열의 길이와 부분수열을 출력하는 문제.

증가 수열의 길이는 DP를 이용하여 쉽게 구할 수 있습니다.

 

 

 

우선 증가수열의 길이부터 구해봅시다.

 

1. dp 배열 값을 모두 1로 초기화 합니다.

: v 배열에서 모든 인덱스의 배열값은 증가 수열의 시작이 될 수 있기 때문에 1로 초기화 해줍니다.

 

 

2. 0번째부터 n-1번째 까지 이중 포문으로 현재 인덱스 위치의 값보다 다음 인덱스 위치(j번째)의 값이 더 크다면

dp 배열의 j번째 값과, i번째 값 + 1중 큰 값을 dp배열의 j번째 값에 삽입합니다.

 

 

3. 가장 긴 증가하는 부분 수열을 출력

 

dp 배열을 이용하여 역추적하여 증가하는 부분수열을 쉽게 구할 수 있습니다.

역추적하지 않고 dp값이 1인 배열부터 순서대로 가장 큰 길이인 4까지 가는 방법도 있지만,
추적과정에서 가장 큰 길이인 4를 알 수 없으므로 끝에서부터 역추적하는 과정이 훨씬 단순.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int n;

vector<int> v(1001,0);
int d[1001];
int ans;

stack<int> st;
int main()
{
    FASTio;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        cin >> v[i];
        d[i] = 1;
    }

    for(int i=0;i<n;i++)
    {  
        for(int j=i+1;j<n;j++)
        {
            if(v[j] > v[i])
            {   
                d[j] = max(d[i] + 1, d[j]);
            }
        }
    }

    for(int i=0;i<n;i++)
    {   
        ans = max(ans, d[i]);
    }

    cout << ans << endl;

    int k = 1;

    for(int i=0;i<n;i++)
    {
        if(d[i]==k)
        {
            st.push(v[i]);
            k++;
        }
    }
    while(!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();

    }
    return 0;
}