[c++] 백준 14002 가장 긴 증가하는 부분 수열 4 (최장 증가 부분 수열 / LIS / Longest Increasing)

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

LIS (Longest Increasing Subsequence)

주어진 '수열' 에서 일부 원소를 뽑아내어 새로만든 수열이 '부분 수열'
이 수열이 '오름차순' 인 수열이 '증가하는 부분 수열' 이 된다.
만들 수 있는 오름차순 수열 중, '가장 긴' 수열이 LIS가 된다.

가장 긴 증가하는 부분수열 시리즈의 코드와 거의 유사하나, 가장 증가하는 부분 수열의 길이 + 수열을 출력해야한다.

수열을 저장하고 출력하는 부분의 코드가 추가되었다.

LIS 코드

arr배열을 탐색하며 증가 수열이 가능한 경우 dp배열을 갱신시켜준다.

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

수열 저장

최장길이인 temp값을 --시켜주면서 해당되는 값을 벡터에 저장

int temp = res;
for (int i = n - 1; i >= 0; i--) {
    if (temp == 0) break;
    if (dp[i] == temp) {
        v.push_back(arr[i]);
        temp--;
    }
}

후 벡터를 뒤에서 부터 출력해 주었습니다.

전체코드

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

using namespace std;

int n, arr[1005], dp[1005];
vector<int> v;

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    fill(dp, dp + n, 1);

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

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > res) res = dp[i];
    }
    int temp = res;
    for (int i = n - 1; i >= 0; i--) {
        if (temp == 0) break;
        if (dp[i] == temp) {
            v.push_back(arr[i]);
            temp--;
        }
    }

    cout << res << "\n";
    for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";

    return 0;
}