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

문제

https://www.acmicpc.net/problem/14002
11053번과 동일한데 이 문제는 수열의 길이와 부분 수열을 출력해야하는 문제다.

풀이

LIS의 길이를 O(n^2)으로 구하는 방법을 이용한 풀이

1. LIS 길이 구하기

부분 수열 길이를 저장하는 배열 c
입력받은 수열을 순회하면서 0번째부터 현재 index까지 순회한다 (2중 for문)
만약 나보다 앞에 나왔는데 나보다 크기가 작으면 c[i] = max(c[j] +1, c[i])

2. LIS 출력하기

LIS길이가 저장된 배열을 역추적해서 LIS의 수열을 뽑아낼 수 있다.
LIS배열을 역순으로 순회하면서 LIS 길이를 값으로 갖으면 stack에 push하고 LIS 길이를 1씩 줄이는 과정을 반복한다.
그리고 stack원소들을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n, res = 1, a[1001], c[1001];
stack<int> s;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++)
    {
        c[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i])
            {
                c[i] = max(c[j] + 1, c[i]);
                res = max(res, c[i]);
            }
        }
    }
    cout << res << "\n";
    for (int i = n - 1; i >= 0; i--)
    {
        if (c[i] == res)
        {
            s.push(a[i]);
            res--;
        }
    }
    while (s.size())
    {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}