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

흔한 LIS 문제였으며 DP를 이용해 푸는 방식이다.

LIS는 자주 풀고 유명한 문제이므로 어려움은 없었지만 수열을 출력하는게 추가되었다.

수열을 출력하기 위해서 parent를 이용한 재귀함수를 이용해 출력하였다. 

문제링크 : 14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void PRINT(vector<int> p, int ind, vector<int> arr) {

	if (ind == -1)
		return;

	PRINT(p, p[ind], arr);
	cout << arr[ind] << ' ';
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	vector<int> arr(N, 0);
	vector<int> DP(N, 1);
	vector<int> parent(N, -1);
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	for (int i = 1; i < N; i++)
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j] && DP[i] < DP[j] + 1)
			{
				DP[i] = DP[j] + 1;
				parent[i] = j;
			}

	int max_ind = max_element(DP.begin(), DP.end()) - DP.begin();
	int max_val = arr[max_ind];

	cout << DP[max_ind] << '\n';

	PRINT(parent, max_ind, arr);
	cout << '\n';

	return 0;
}