[C/C++] BOJ 14002 :: 가장 긴 증가하는 부분 수열 4

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

문제 링크 : https://www.acmicpc.net/problem/14002

나의 풀이

1. 현재 idx의 수가 부분 수열의 마지막 수가 될 때, 이전 수의 arr의 idx와 부분 수열의 길이를 저장하는 구조체 배열을 만든다.

2. 다이나믹 프로그래밍 방식으로 부분 수열을 구하면서 수열의 이전 값을 갖는 arr의 idx를 저장한다.

3. 가장 긴 증가하는 부분 수열의 마지막 값에서부터 이전 값을 차례대로 스택에 넣은 뒤, 스택에서 빼내면서 출력한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_14002/BOJ_14002.cpp

// 백준알고리즘 14002번 :: 가장 긴 증가하는 부분 수열 4
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
 
struct info
{
    int len;
    int prev;
}typedef INFO;
 
int N;
int arr[1001];
INFO lis[1001];
 
int main()
{
    stack<int> st;
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    for (int i = 0; i < N; i++) {
        lis[i].len = 1;
        lis[i].prev = -1;
        
        for (int j = 0; j < i; j++)
        {
            if (arr[j] < arr[i] && (lis[i].len < lis[j].len + 1))
            {
                lis[i].len = lis[j].len + 1;
                lis[i].prev = j;
            }
        }
    }
 
    int idx = 0;
    int ans = lis[0].len;
    for (int i = 1; i < N; i++)
    {
        if (ans < lis[i].len) {
            ans = lis[i].len;
            idx = i;
        }
    }
    cout << ans << '\n';
 
    while (idx != -1)
    {
        st.push(arr[idx]);
        idx = lis[idx].prev;
    }
 
    while (!st.empty())
    {
        cout << st.top() << ' ';
        st.pop();
    }
 
    return 0;
}