가장 긴 증가하는 부분 수열 4 (feat. 백준, 14002번)

가장 긴 증가하는 부분 수열 4
https://www.acmicpc.net/problem/14002

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

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/14002
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, arr[1001], dp[1001] = { 0 };
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i], dp[i] = 1;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= i; ++j)
			if (arr[j] < arr[i])		dp[i] = max(dp[i], dp[j] + 1);
	auto max_index = max_element(dp + 1, dp + 1 + N) - (dp + 1) + 1;		// dp[1] ~ dp[N] 중 최대값을 갖는 인덱스 (1부터)
	cout << dp[max_index] << "\n";
	priority_queue<int, vector<int>, greater<int>> q;
	q.push(arr[max_index]);
	for (register int i = max_index - 1; i >= 1; --i)		// 최대값을 갖는 인덱스부터 아래로
		if (dp[max_index] - 1 == dp[i])
			q.push(arr[i]), max_index = i;
	while (!q.empty())
		cout << q.top() << " ", q.pop();
	return 0;
}
// *&)*@*

설명하기 전에 해당 문제의 모태급이 되는 "가장 긴 증가하는 부분" 문제를 먼저 풀어보시길 권장합니다.

가장 큰 증가 부분 수열 (feat. 백준, 11055번)

 

1. 정답의 첫번째 줄은 가장 긴 개수에 대한 답이므로 위의 "가장 긴 증가하는 부분" 의 정답과 동일합니다.
2. 문제는 어떤 항목들이 개수에 포함되었는가 만 생각하면 됩니다.
3. 따라서 가장 긴 개수를 갖는 위치를 먼저 찾습니다.
4. 그리고 그 위치로부터 (N이라고 하면) 아래쪽의 dp 배열을 검사합니다. (1 ~ N-1 에 대해서)
5. 즉, dp의 값이 1 2 3 2 1 2 4 3 2 5 6 3 2 1 이라고 한다면, 6이 가장 긴 개수의 정답이 되겠고 6보다 아래의 dp 배열 중 5, 4, 3, 2, 1 이 있는 위치에 해당되는 입력받은 값 을 출력하면 됩니다.