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

문제 출처: https://www.acmicpc.net/problem/14002

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

가장 긴 증가하는 부분 수열을 구하면서 visited배열을 만들어 경로를 역추적 할 수 있도록 하여 해결함.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

int arr[1001];
int dp[1001];
int visited[1001];
int maxroot;


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

    int N; cin >> N;
    for (int i = 0; i < N; i++) { 
        cin >> arr[i];
        dp[i] = 1;
    }

 
    
    int max = 1;

    for (int i = 0; i < N; i++) {
        for (int prev = 0; prev < i; prev++) {
            if (arr[i] > arr[prev]) {
                if (dp[i] < dp[prev] + 1) {
                    visited[i] = prev;
                    dp[i] = dp[prev] + 1;
                    if (max < dp[i]) { 
                        maxroot = i;
                        max = dp[i]; 
                    }
                }
            }
        }
    }

    cout << max<<'\n';

    int next=maxroot;
    vector<int>v;
    for (int i = 0; i < max; i++) {
       v.push_back(arr[maxroot]);
        maxroot = visited[maxroot];
    }

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

}