[BAE/<JOON> 문제풀이] 2550. 전구

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

2550번: 전구

핵심::

n log n LIS 알고리즘

 

풀이::

스위치의 위치와 전구의 위치들의 상대적 인덱스를 배열로 만들고 LIS를 찾는다.

 

의견::

n log n LIS 문제가 플레 5인데 왜 그걸 응용한 이 문제 골드3인지 잘 모르겠다.

 

코드::

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

using namespace std;

struct trackball {
	int idx, val;
};

int main()
{
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	vector<int> dp;
	vector<trackball> track(n + 1);

	vector<int> i1(n + 1);

	for (int i = 1; i <= n; i++) {
		cin >> i1[i];
	}
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		for (int j = 1; j <= n; j++) {
			if (i1[j] == a) {
				arr[j] = i;
			}
		}
	}	

	dp.push_back(arr[1]);
	track[1] = { 0, arr[1] };
	for (int i = 2; i <= n; i++) {
		if (arr[i] > * (dp.end() - 1)) {
			dp.push_back(arr[i]);
			track[i] = { (int)dp.size() - 1, i };
		}
		else {
			auto lb = lower_bound(dp.begin(), dp.end(), arr[i]);
			*lb = arr[i];
			track[i] = { lb - dp.begin(), i };
		}
	}

	cout << dp.size() << "\n";

	vector<int> path;
	int tc = dp.size() - 1;
	for (int i = n; i >= 1; i--) {
		if (track[i].idx == tc) {
			path.push_back(track[i].val);
			tc--;
		}
		if (tc == -1) break;
	}

	vector<int> dap;
	for (int i = path.size() - 1; i >= 0; i--) {
		dap.push_back(i1[path[i]]);
	}

	sort(dap.begin(), dap.end());

	for (auto v : dap) {
		cout << v << " ";
	}

	return 0;
}