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

https://www.acmicpc.net/problem/14002

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

---

문제 풀이

 LIS 1번 문제에서 다음 버전으로 LIS의 길이와 LIS 자체를 출력해야한다.

배열 L은 LIS의 길이를 구하기 위한 배열이고 배열 P는 arr의 원소들의 lower_bound를 저장하는 배열이다.

함수 Backtrace는 배열 P에 저장된 lower_bound로 LIS를 출력하는 재귀함수이다.  

P[i]와 길이와 같다면 arr[i]의 값을 출력하고 아니라면 P[i-1]와 비교해서 계속 출력한다.

느낀 점

처음에 L 배열에 저장된 값이 LIS의 값이 아니라는 사실을 이해 못해서 어려웠다. 출력을 하면 내가 아는 LIS의 값과 동일하게 출력이 되었기 때문이다. 하지만 단순히 L은 LIS의 길이를 나타내기 위한 배열임을 이해하고 따로 배열을 추가해 LIS의 원소들의 인덱스를 저장한 뒤 백트래킹으로 출력해야했던 것이다. LIS에 대해서 많이 이해한 계기가 되었다. 

코드

#include <iostream>

using namespace std;

int n;
int arr[1001], L[1001], p[1001];

int binary(int left, int right, int key) {
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (L[mid] >= key) right = mid - 1;
		else left = mid + 1;
	}
	return left;
}

void backtrace(int idx, int len) {
	if (idx < 0) return;
	if (p[idx] == len) {
		backtrace(idx - 1, len - 1);
		cout << arr[idx] << " ";
	}
	else backtrace(idx - 1, len);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
	int idx = 0;
	for (int i = 0; i < n; i++) {
		if (L[idx] < arr[i]) L[++idx] = arr[i];
		else {
			int lower_bound = binary(0, idx, arr[i]);
			L[lower_bound] = arr[i];
		}
		p[i] = binary(0, idx, arr[i]) + 1;
	}
	cout << idx + 1 << "\n";
	backtrace(n, idx + 1);
}