[DP] BOJ 14002 가장 긴 증가하는 부분 수열 4

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

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

- 문제 파악

주어지는 수열에서 적절히 수를 제거하여 증가하는 수열을 만드는데 길이가 가장 긴 수열의 길이와 그 수열을 출력하라.

 

-정답

 

기본적으로 https://dhjkl123.tistory.com/58 문제와 같고 추가 적으로 가장 긴 증가하는 부분 수열을 출력하는 문제이다.

 

D배열에 넣는 길이가 변할 때마다 영향을 준 수열의 위치를 Darr에 넣도록 했다. 거꾸로 찾아가면 가장 작은 수에 도달할 수 있다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[1001]; 
int arr[1001];
int ans = 1;
int Darr[1001];
int ansarr[1002];


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	fill(D, D + 1001, 1);
	fill(Darr, Darr + 1001, -1);
	
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (arr[i] < arr[j])
			{
				int ntmp = D[j];
				D[j] = max(D[j], D[i] + 1);

				if (ntmp != D[j])
				{
					Darr[j] = i;
				}

			}
		}
	}
	
	int nMaxPos = -1;

	for (int i = 0; i < n; i++)
	{
		int ntmp = ans;
		ans = max(D[i], ans);

		if (ntmp != ans)
		{
			nMaxPos = i;
		}

	}

	int k = 0;

	if (nMaxPos == -1)
	{
		ansarr[0] = arr[0];
		k++;
	}
	
	while (nMaxPos != -1)
	{		
		ansarr[k] = arr[nMaxPos];
		k++;
		nMaxPos = Darr[nMaxPos];
		
	}

	cout << ans << "\n";

	for (int i = k-1; i >= 0; i--)
	{
		cout << ansarr[i] << " ";
	}


}