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

#문제

www.acmicpc.net/problem/14002

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

 

#풀이 & 학습한 내용

앞서 풀었던 supremo7.tistory.com/92에서 길이만을 구하는 것이 아닌 부분 수열 자체를 출력해줘야 한다. 이때는 추가로 dp배열에서 역추적하는 배열을 만들어 그 전의 index가 어디인지 저장한다. 그리고 재귀를 통해 출력해준다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
void printr(int find_i);
 
using namespace std;
 
int dp[1001][2];
int p[1001];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
    }
 
    for (int i = 1; i <= N; i++) {
        dp[i][0] = 1;
        dp[i][1] = i;
        for (int j = 1; j <= i; j++) {
            if (p[j]<p[i] && dp[j][0] + 1>dp[i][0]) {
                dp[i][0] = dp[j][0] + 1;
                dp[i][1] = j;
            }
        }
    }
 
    int max_ind = 1;
    for (int i = 2; i <= N; i++) {
        if (dp[max_ind][0] < dp[i][0])
            max_ind = i;
    }
 
    cout << dp[max_ind][0] << '\n';
    printr(max_ind);
}
 
void printr(int find_i) {
    if (dp[find_i][1] == find_i) {
        cout << p[find_i]<<" ";
        return;
    }
    printr(dp[find_i][1]);
    cout << p[find_i]<<" ";
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_14002.cpp

HoYoungChun/BOJ_algorithm