[ 백준][DP] 가장 긴 증가하는 부분수열 4

1. 문제 주소

 

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

2. 문제

이 전에 풀었던 가장 긴 증가하는 부분수열 문제의 응용 문제이다. 이전에는 가장 긴 부분 수열의 길이만을 출력하였지만 이 문제는 부분 수열까지 출력을 해야한다. 언제 수열의 길이가 증가하는지 확인하고 그 때의 index를 배열에 저장을 하여 재귀함수를 이용하여 수열을 출력하였다.

 

3. 소스 코드

#include <iostream>
using namespace std;
 
int n[1000];
int length[1000];
int index[1000];
 
void print(int longestindex)
{
    if (longestindex == -1) return;
    print(index[longestindex]);
    cout << n[longestindex] << ' ';
}
 
int main(void)
{
    int a;
    cin >> a;
 
    for (int i = 0; i < a; i++)
    {
        cin >> n[i];
    }
 
    for (int i = 0; i < a; i++)
    {
        length[i] = 1;
        index[i] = -1;
        for (int j = 0; j < i; j++)
        {
            if (n[i] > n[j] && length[i] == length[j]) {
                length[i] = length[j] + 1;
                index[i] = j;
            }
        }
    }
 
    int longestlength = 0;
    int longestindex = 0;
    for (int i = 0; i < a; i++)
    {
        if (longestlength < length[i]) {
            longestlength = length[i];
            longestindex = i;
        }
    }
    cout << longestlength << '\n';
    print(longestindex);
    cout << '\n';
    
    return 0;
}