백준 14002 가장 긴 증가하는 부분 4 (C++)

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

dp를 이용한 문제이다. 먼저 반복문을 돌면서 가장 긴 길이와 그에 해당하는 인덱스를 dp를 이용해 구해준다. 그리고 반대로 반복문을 돌면서 len을 1씩 빼면서 dp와 비교하여 같을 경우 벡터에 저장한 후 정렬한 뒤 출력해주었다. 생각보다 어려웠던 문제였다. 최댓값을 구해서 이를 이용해 이전 인덱스를 어떻게 찾아야할지 떠오르지가 않았었다. 이러한 방식도 기억해두어야 겠다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int A[1000];
int dp[1000];
int len = 0;
vector<int> v;

void solution() {
    for (int i = 0; i < N; i++) {
        dp[i] = 1;

        for (int j = 0; j < i; j++) {
            if (A[j] < A[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }

        if (len < dp[i]) {
            len = dp[i];
        }
    }

    for (int i = N - 1; i >= 0; i--) {
        if (len == dp[i]) {
            v.push_back(A[i]);
            len--;
        }
    }

    sort(v.begin(), v.end());

    cout << v.size() << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
}

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

    cin >> N;

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

    solution();

    return 0;
}