BOJ : 14003 가장 긴 증가하는 부분 수열5

 

---

[BOJ 14003(G1)리뷰]

가장 긴 증가하는 부분수열 문제 시리즈를 풀었다.

이 문제들을 푸는데 필요한 알고리즘인 LIS알고리즘을 정리해놓았다.

이 문제는 시리즈 중 가장 어려운 문제이다.

입력데이터가 1,000,000이므로 O(N²)로는 풀수가 없고 lower bound를 이용하여 O(NlogN)으로 풀어야 한다.

게다가 이 문제는 부분 수열까지 출력해야 하는 조건이 있다.

 

부분 수열을 출력하기 위하여 trace라는 스택에 각 값의 lower bound를 기록했다.

만약 {10,20,10,30,20,50} 이라면 lower bound는 {1,2,1,3,2,4} (인덱스 1부터 시작) 가 된다.

그리고 가장 긴 증가하는 부분수열의 길이는 4가 된다.

이제 뒤에서부터 <-방향으로 lower bound 데이터를 읽으며 현재 길이가 가장 먼저 등장하는 lower bound의 index가 우리가 출력해야할 값들이다. 

따라서 {1,2,1,3,2,4}의 인덱스를 기록하여 이것의 데이터를 출력하면 된다.

출력은 앞부터 진행하기 위해 백트래킹을 이용했다.

 

---

#include <bits/stdc++.h>
using namespace std;

vector <int> arr;
stack <int> trace;

void backtrace(int size)
{
	if (size == 0) return;
	int cur = trace.top();
	if (cur == size - 1)
	{
		int idx = trace.size()-1;
		trace.pop();
		backtrace(size - 1);
		cout << arr[idx] << ' ';
	}
	else
	{
		trace.pop();
		backtrace(size);	
	}

}

int main(void)
{
	int N;
	cin >> N;

	vector <int> list;
	int maxidx = 0;
	for (int i = 0; i < N; i++)
	{
		int val;
		cin >> val;
		arr.push_back(val);

		if (list.empty() || list.back() < arr[i])
		{
			list.push_back(arr[i]);
			trace.push(maxidx);
			maxidx++;
		}
		else
		{
			auto pos = lower_bound(list.begin(),list.end(),arr[i]);
			*pos = arr[i];
			trace.push(distance(list.begin(), pos));
		}
	}

	int size = list.size();
	cout << size << "\n";
	backtrace(size);
}