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

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

 

 

가장 긴 증가하는 부분 수열을 선행했다면 굉장히 쉽게 풀 수 있는 문제였습니다.

 

풀이

int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>num[i];
        dp[i] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(dp[i] == dp[j] && num[i] > num[j]) dp[i]++;
        }
    }

먼저 위와 같이

dp[i] = i번째 숫자가 끝일 때, 가장 긴 증가하는 부분 수열의 길이로 설정하고,

그 값을 구해줍니다.

 

 

한 개의 원소로 구성된 수열은 값이 1이기에 초깃값으로 설정해주고,

원소의 범위를 늘려가며 가장 긴 증가하는 부분 수열의 길이를 구해줍니다.

 

 

조건문의 조건에 대해 살펴보겠습니다.

먼저, 증가하는 부분 수열이기에 num[i] > num[j]는 자명합니다.

dp[i]  == dp[j]를 비교하는 이유는 중복되는 카운트를 제거하기 위함입니다.

 

 

dp[j]는 j를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이입니다.

j에서 i번째 숫자를 추가했을 때, dp[i]가 i를 끝으로 하는 가장 긴 증가하는 부분 수열이 되기 위해서

위와 같이 dp[i]  == dp[j], num[i] > num[j] 두 가지 조건으로 dp 배열 값을 갱신합니다.

 

1부터 i-1까지 탐색했을 때, dp배열의 값이 j까지 탐색했을 때와 동일해야만

num[j] 다음으로 num[i]를 가지는 부분수열을 구할 수 있습니다.

{... num[j]    num[i]}

 

 

그 후에 가장 긴 증가하는 부분 수열의 원소들을 출력해야 하는데,

어떻게 하면 좋을까요???

 

 

이는 dp배열을 이용해 역추적해주면 쉽게 할 수 있습니다!

 

 

먼저 dp배열을 탐색하면서,

가장 긴 증가하는 부분 수열의 마지막 원소의 위치를

가장 긴 증가하는 부분 수열의 길이를 찾으며 함께 찾습니다.

int myMax = -1;
    int idx = 0;
    for(int i = 1; i <= n; i++){
        if(myMax < dp[i]){
            myMax = dp[i];
            idx = i;
        }
    }

 

 

코드를 따라 idx에 그 원소의 위치가 저장이 되고,

num[idx]의 값을 int형 벡터에 push해줍니다.

vector<int> ans;
ans.push_back(num[idx]);

 

 

그 후 idx부터 1까지 dp배열의 값을 역순으로 탐색해줍니다.

 

dp[idx]보다 1 작은 값을 가지는 dp[i]는

num[idx]를 끝으로 하는 가장 긴 증가하는 부분 수열에서

num[idx]를 포함하지 않았을 때 가장 긴 증가하는 부분 수열의 끝이었을겁니다!

 

 

그럼 그 찾은 값인 num[i]를 벡터에 넣어주고

idx = i로 갱신해줍니다.

이 과정을 끝까지 반복하면 역추적을 성공적으로 해낼 수 있습니다.

 

for(int i = idx; i >= 1; i--){
        if(dp[idx] == dp[i] + 1){
            ans.push_back(num[i]);
            idx = i;
        }
    }

 

 

 

마지막으로 끝에서부터 차례대로 출력해주면 원하는 출력값을 얻을 수 있습니다.

int size = ans.size();
    for(int i = size-1; i >= 0; i--){
        cout<<ans[i]<<" ";
    }

 

 

 

 

전체 코드

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

int dp[1005];
int num[1005];

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

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>num[i];
        dp[i] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(dp[i] == dp[j] && num[i] > num[j]) dp[i]++;
        }
    }

    int myMax = -1;
    int idx = 0;
    for(int i = 1; i <= n; i++){
        if(myMax < dp[i]){
            myMax = dp[i];
            idx = i;
        }
    }
    cout<<myMax<<"\n";

    vector<int> ans;
    ans.push_back(num[idx]);
    for(int i = idx; i >= 1; i--){
        if(dp[idx] == dp[i] + 1){
            ans.push_back(num[i]);
            idx = i;
        }
    }

    int size = ans.size();
    for(int i = size-1; i >= 0; i--){
        cout<<ans[i]<<" ";
    }
    
    return 0;
}

 

DP배열의 역추적 개념에 대해 배울 수 있었던 문제였습니다!