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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

 

점화식 d[i] // i를 마지막으로 하는 수열 중 가장 긴 길이.

i : 0 ~ N 까지 반복하면서  j : 0 ~ i 범위에서 d[j]는 j를 마지막으로 하는 수열이므로 num[j] < num[i] && d[i] < d[j] + 1 이라면 d[j]에 num[i]를 추가하는 수열로 길이 늘리면 된다.

 

이 경로 찾는 방법은 

v[i] // i를 마지막으로 하는 수열 중 가장 긴 수열이 완성될 때 i 이전의 인덱스를 저장.

 

d[i]의 저장이 끝나고 가장 긴 수열을 찾을 때 maxi로 그 때의 마지막 인덱스를 구한다.

그 인덱스로 부터 v[maxi]하면 그 이전 인덱스를 구할 수 있고

반복해서 타고 가면 됨.

 

최대인 수열의 길이만큼 !

 

 

 

 

#include <iostream>
#include <string.h>
#include <deque>
#include<queue>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;
int arr[1000];
int d[1000]; // i를 가장 마지막으로 하는 증가 수열의 최대 길이 
int v[1000];
int N;

int main(void)
{
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	for (int i = 0; i < N; i++)
	{
		d[i] = 1;
		v[i] = 0;
		for (int j = 0; j < i; j++)
		{
			if (arr[j] < arr[i] && d[i] < d[j] + 1)
			{
				d[i] = d[j] + 1;
				v[i] = j; //i를 마지막으로 하는 수열의 이전 원소 
			}
		}
	}

	int maxa = 0;
	int maxi = 0;

	for (int i = 0; i < N; i++)
	{
		if (maxa < d[i])
		{
			maxa = d[i];
			maxi = i;
		}
	}
	cout << maxa << endl;
	int ans[1000]; // 정답 저장 maxi 부터 타고 가기.

	for (int i = 0; i < maxa; i++)
	{
		ans[i] = arr[maxi];
		maxi = v[maxi]; // 이전 인덱스로 
	}

	for (int i = maxa - 1; i >= 0; i--)
	{
		cout << ans[i] << " ";
	}
	cout << endl;

	return 0;
}