[백준] C++ 14002(가장 긴 증가하는 부분 수열 4)

 

#include <iostream>

using namespace std;

int arr[1001];
int DP[1001];
int result[1001];

int main(void)
{
	int A=0;
	
	cin>>A;
	
	for(int i=0; i<A; i++)
	{
		cin>>arr[i];
	}
	
	int max=0;
	int index=0;
	
	for(int i=0; i<A; i++)
	{
		for(int j=0; j<i; j++)
		{
			if(arr[i]>arr[j]&&DP[i]<DP[j]+1)
			{
				DP[i]=DP[j]+1;
			}
			if(max<DP[i])
			{
				max=DP[i];
				index=i;
			}
		}
	}
	
	cout<<max+1<<endl;
	
	int count=0;
	
	for(int i=index; i>=0; i--)
	{
		if(DP[i]==max)
		{
			result[count]=arr[i];
			count++;
			max--;
		}
	}
	
	for(int i=count-1; i>=0; i--)
	{
		cout<<result[i]<<" ";
	}
	
	return 0;
}

수열 A의 가장 긴 증가하는 부분 수열의 길이와 부분 수열을 출력하는 문제이다.

증가하는 부분 수열의 길이는 쉽게 구할 수 있다.

if(arr[i]>arr[j]&&DP[i]<DP[j]+1) 
{
		DP[i]=DP[j]+1;
}

 

 

50을 기준을 살펴보겠다. 50보다 작은 수는 10, 20 ,10 ,30 ,20이 있다. 이 중에서 가장 긴 수열을 가지고 있는 수는 30이다.

2+1=3이라는 값이 나온다. 즉 50보다 작은 수는 3개가 있다는 말이다.

? ? ? 50의 길이는 4

여기서 ?는 어떻게 알 수 있을까??

역으로 이동하면 된다.

최댓값이 나온 인덱스부터 수열의 길이를 하나씩 줄여가면서 순서대로 찾아주면 된다.(그림으로 설명하겠다.)

for(int i=index; i>=0; i--)
{
	if(DP[i]==max)
	{
		result[count]=arr[i];
		count++;
		max--;
	}
}
	
for(int i=count-1; i>=0; i--)
{
	cout<<result[i]<<" ";
}