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

문제링크 : https://www.acmicpc.net/problem/14002

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[1001];
int dp[1001];
int len = 0;
vector<int>v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        dp[i]=1; //최소길이는 1
        for(int j=0; j<i; j++)
        {
            if(arr[j]<arr[i]) dp[i] = max(dp[i], dp[j]+1); //길이 증가
        }
        len = max(dp[i], len); //최대 길이 저장
    }
    cout << len <<"\n";
    
    for(int i=N-1; i>=0; i--)
    {
        if(dp[i]==len) //맞는 길이에 대해 출력
        {
            v.push_back(arr[i]);
            len--; //값을 하나 추가했으므로 길이도 감소
        }
    }

    for(int i=v.size()-1; i>=0; i--) //push_back이었으므로 뒤에서부터 출력
    {
        cout << v[i] << " ";
    }
    return 0;
}

 

우선 가장 긴 증가하는 부분수열의 길이를 구해준다.

모든 수에 대해서 최소 길이는 1이므로 dp를 1로 초기화로 해주고, 현재값과 그전값들을 비교하여 길이가 증가할 수 있다면 증가한 값을 dp에 저장해준다.

길이 체크를 마친 후에 최대 길이를 또 따로 저장해준다.

 

dp에 길이가 큰 값은 주로 뒤에 위치해있고,

내가 접근할 길이또한 큰 값이므로 반복문의 인덱스를 맨 뒤에서부터 시작해준다.

뒤에서부터 dp 배열을 탐색하며 현재 최대 사이즈와 dp의 값이 같다면 해당 인덱스의 arr 배열의 값을 따로 벡터에 담아준다.

이렇게 값을 하나 추가했으면 해당 길이의 값은 이제 탐색하지 않으므로 길이를 하나 줄여서 다음 길이의 값을 탐색한다.

위 과정을 반복하여 맞는 길이에 대해 벡터에 담아준다.

<예제>
값 : 길이
10 : 1
20 : 2
10 : 1
30 : 3
20 : 2
50 : 4

제일 긴 길이 -> 4부터 시작해서 1까지 진행 (4 -> 3 -> 2-> 1)

 

벡터의 경우 puch_back으로 뒤에서 부터 값을 담았기에 출력을 해줄때는 인덱스를 뒤에서 부터 접근하여 원래의 순서대로 출력해주도록 한다.