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

12 Feb 2021 in Algorithm

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

나의 풀이

이 문제는 11722 가장 긴 감소하는 부분 수열과 유사하게 DP로 해결할 수 있다. 기존 문제와 다르게 이 문제는 부분 수열의 길이뿐만 아니라 가장 긴 부분 수열을 하나 출력해야 하기 때문에 이 부분을 추가로 처리해주어야 한다.

• DP[i].fisrt = 가장 긴 증가하는 부분 수열의 마지막 값이 A[i]인 수열의 길이를 의미한다.
• DP[i].second =DP[i].fisrt에서 구한 수열 중 뒤에서 2번째 값의 인덱스를 의미한다. 예를 들어 A = {10, 20, 30, 10} 일 때 다음과 같은 값을 갖게 된다.
  DP[0].first = 1, DP[0].second = 0 (길이가 1이면 자기 자신의 인덱스 의미함)
  DP[1].first = 2, DP[1].second = 0 (수열 {10, 20} 중 10의 인덱스)
  DP[2].fisrt = 3, DP[2].second = 1 (수열 {10, 20, 30} 중 20의 인덱스)
  DP[3].fisrt = 1, DP[3].second = 3 (길이가 1이면 자기 자신의 인덱스)
  같은 방식으로 모든 DP 값을 구하면 DP 중 first 값의 최대를 찾고, 그 때의 인덱스를 시작으로 DP[i].second로 역추적하면 부분 수열의 이전 값까지 찾을 수 있고 이 과정을 반복하면 모든 부분 수열을 출력할 수 있다.

  풀이 코드 : 14002 가장 긴 증가하는 부분 수열4

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

pair<int, int> DP[1000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, num;
    vector<int> A;
    cin>>N;
    
    for(int i=0;i<N;i++){
        cin>>num;
        A.push_back(num);
        DP[i].first = 1;
        DP[i].second = i;
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<i;j++){
            if(A[j] < A[i])
            {
                if(DP[j].first + 1 > DP[i].first){
                    DP[i].first = DP[j].first + 1;
                    DP[i].second = j;
                }
            }
        }
    }

    int len = 0;
    int idx;
    for(int i=0;i<N;i++){
        if(len <DP[i].first) {
            len = DP[i].first;
            idx = i;
        }
    }

    vector<int> result;
    for(int i=0;i<len;i++){
        num = A[idx];
        result.push_back(num);
        idx = DP[idx].second;
    }
    cout<<len<<"\n";
    while(!result.empty()){
        num = result.back();
        result.pop_back();
        cout<<num<<" ";
    }
}

채점결과