백준 - 14002번 : 가장 긴 증가하는 부분 수열 4 (C++)

풀이 방법 : DP

유명한 시리즈의 문제 DP테이블에 각 자리까지의 최대 길이를 갱신해주면 된다. 이전 시리즈의 문제와 다른 점은 그때까지의 경로를 함께 저장해주어야 한다는 점이다.

이중 포문을 돌려주면서 이전의 숫자보다 현재 숫자가 더 큰 경우에 길이를 비교하고 이전까지의 경로에 현재 숫자를 더해주는 것이 길이가 더 긴 경우 현재의 경로를 갱신해준다.

#include <iostream>
#include <vector>

using namespace std;

int N;
int Nums[1001] = {};
vector<int> DP[1001] = {};

int main()
{
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> Nums[i];
		DP[i].push_back(Nums[i]);
	}

	for (int i = 1; i < N; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (Nums[j] < Nums[i])
			{
                int SrcSize = DP[i].size();
                int DestSize = DP[j].size();
            
				if (SrcSize < DestSize + 1)
				{
					DP[i] = DP[j];
					DP[i].push_back(Nums[i]);
				}
			}

		}
	}

	int Idx = 0;

	for (int i = 1; i < N; ++i)
	{
		if (DP[Idx].size() < DP[i].size())
			Idx = i;
	}

	int Size = DP[Idx].size();
	cout << Size << '\n';

	for (int i = 0; i < Size; ++i)
	{
		cout << DP[Idx][i] << ' ';
	}
}