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

문제

접근 방법

LIS를 이용하여서 풀면 된다.
가장 긴 경우에만 인덱스를 저장해준다. LIS가 끝났다면 가장 긴 경우에 대한 인덱스가 남는데 그 인덱스에서 시작하여 길이를 1씩 감소시켜주면 가장 긴 증가하는 부분 수열을 구할 수 있다.

1 5 4 7 2 3의 경우 7이 가장 긴 경우에 대한 인덱스이다.
7에서 시작하면 7이 3의 길이를 가지고 있기에 길이를 감소시켜주고 저장해준다. 그다음 확인해보면 4가 2의 길이를 가지고 있다. 이런 식으로 반복하면 7 4 1을 저장할 수 있다. 이것을 스택의 형태로 출력하면 1 4 7이라는 값을 출력하게 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, maxIdx = 0, maxSize = 0;
    cin >> N;
    vector<int> A, dp(N), ret;
    for (int i = 0; i < N; ++i)
    {
        int a;
        cin >> a;
        A.push_back(a);
        dp[i] = 1;
        for (int j = 0; j < i; ++j)
        {
            if (A[i] > A[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        if (dp[i] > maxSize)
        {
            maxSize = dp[i];
            maxIdx = i;
        }
    }
    cout << maxSize << "\n";
    for (int i = maxIdx; i >= 0; --i)
    {
        if (dp[i] == maxSize)
        {
            ret.push_back(A[i]);
            --maxSize;
        }
    }
    for (int i = ret.size() - 1; i >= 0; --i)
    {
        cout << ret[i] << " ";
    }
}

풀이

LIS를 하는 법, 인덱스를 저장하고 활용하는 법을 확인하는 문제이다.
실수로 if (A[i] > A[j]) 안에 가장 긴 증가하는 부분 수열에 대한 인덱스를 갱신하는 부분을 넣었는데 그렇게 하면 수열이 1개인 경우 비교할 것이 없기에 갱신하지 못하고 0을 출력하여 오답으로 처리된다.