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

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

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

 본 문제는 가장 긴 증가하는 부분 수열과 비슷한 문제다. (때문에 자세한 설명은 생략한다.) 가장 긴 증가하는 부분 수열의 길이를 출력하는 것은 동일하나, 가장 긴 증가하는 부분 수열을 출력해야 하는 문제다. 따라서, 점화식을 계산할 때 따로 이전 배열만 저장하면 된다.

Bottom-up

#include <cstdio>
#include <stack>
 
using namespace std;
 
int a[1001];
int d[1001][2];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i <= n; i++) {
        d[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j] && d[i][0] < d[j][0] + 1) {
                d[i][0] = d[j][0] + 1;
                d[i][1] = a[j];
            }
        }
    }
    int ans = 0, chk = 0;
    for (int i = 1; i <= n; i++) {
        if (ans < d[i][0]) {
            ans = d[i][0];
            chk = i;
        }
    }
    stack<int> st;
    st.push(a[chk]);
    for (int i = n; i > 0; i--) {
        if (a[i] == st.top()) st.push(d[i][1]);
    }
    printf("%d\n", ans);
    st.pop();
    while (!st.empty()) {
        printf("%d ", st.top());
        st.pop();
    }
    printf("\n");
}