[백준 C++] 14002 가장 긴 증가하는 부분 수열 4 - 다이나믹프로그래밍

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

#include <iostream>
#include <stack>
using namespace std;

int Sequence[1000];
int DP[1000];
stack<int> LIS;

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

	int Max = 0;

	int Index = 0;
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> Sequence[i];

		for (int j = 0; j < i; ++j)
		{
			if (Sequence[j] < Sequence[i]
				&& DP[j] > DP[i])
			{
				DP[i] = DP[j];
			}
		}

		DP[i] += 1;
		if (DP[i] > Max)
		{
			Index = i;
			Max = DP[i];
		}
	}

	LIS.emplace(Sequence[Index]);

	int j = Index;
	for (int i = Index - 1; i >= 0; --i)
	{
		if (DP[i] == DP[j] - 1)
		{
			LIS.emplace(Sequence[i]);
			j = i;
		}
	}

	cout << Max << '\n';
	while (!LIS.empty())
	{
		cout << LIS.top() << ' ';
		LIS.pop();
	}
}

---

 

다이나믹 프로그래밍으로 최장 증가 수열의 길이와 그 원소를 구하는 문제입니다.

풀이 과정은 다음과 같습니다.

 

첫번째 수부터 N번째 수까지 순차 탐색을 통해서 DP배열에 현재 수까지의 최장 증가 수열 길이를 저장해줍니다.

(반복문 내부에서 현재 수까지의 이전 수를 한번 더 순차 탐색합니다. 현재 수보다 작은 수 중 가장 큰 DP 값을 물려받고 +1해준 값을 저장합니다.)

 

그리고 가장 큰 DP 값을 저장한 인덱스를 기억한 다음,

해당 인덱스부터 역으로 추적하면서 스택 자료구조에 수를 담아줍니다.

해당 인덱스 DP 값부터 -1씩 해가면서 DP 값이 일치하는 수를 담아주면 됩니다.