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

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

기본적으로 DP로 길이만 저장하는 LIS를 구하는 방법에서 조금 변화를 주어

arr 배열엔 입력 값을 저장하고

len 배열엔 길이를 저장하고

dp 배열엔 현재 위치까지에서 가장 긴 수열을 가진 위치를 저장하였다.

 

그러고 출력할 땐 수열의 길이가 가장 길었던 위치부터 재귀 호출하여

그 수열의 처음까지 들어간 다음

출력하면서 빠져나왔다.

#include <iostream>
using namespace std;
int N, arr[1001], dp[1001], len[1001], Max;

void Print(int idx) {
	if (idx == dp[idx]) {
		cout << arr[idx] << " ";
		return;
	}
	Print(dp[idx]);
	cout << arr[idx] << " ";
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		dp[i] = i, len[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) {
				if (len[i] < len[j] + 1) len[i] = len[j] + 1, dp[i] = j;
			}
		}
		if (len[i] > len[Max]) Max = i;
	}
	cout << len[Max] << "\n";
	Print(Max);
	return 0;
}