문제

문제 링크

해설

• N이 최대 100만이므로 DP를 이용해도 O(N²) 알고리즘이기 때문에 시간초과가 납니다.
• LIS의 경우, std::lower_bound()를 이용하면 O(NlogN)에 길이를 구할 수 있습니다.
• 하지만 이때, LIS의 내용물이 계속해서 overwrite되고, 원본 배열의 순서(안정성)가 보장되지 않습니다.
  • 그러므로 LIS의 길이가 아닌 LIS의 내용물을 출력하기 위해서는 한 가지 과정을 더 거쳐야 합니다.
  • 저는vector<pair<int, int>> ans 배열을 따로 만들어서 first에는 LIS에서의 위치를, second에는 값을 저장했습니다.
• 위 ans 배열을 뒤에서부터 탐색하면서 first값이 LIS 인덱스를 거꾸로 탐색합니다. ( 예를 LIS의 길이가 5라면, ans 배열을 뒤에서부터 탐색하면서 first가 4인 것, 3인 것, 2인 것, 1인 것, 0인 것을 찾습니다.)
• 탐색의 편의를 위해 거꾸로 탐색했기 때문에, 올바른 순서로 출력하기 위해 스택을 하나 만들어서 push 후 출력해줍시다.

코드

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1e9 + 1;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;
	
	int len = 0;
	vector<int> lis(N, INF);
	vector<pair<int, int>> ans(N);
	for (int i = 0; i < N; ++i) {
		int key; cin >> key;
		auto pos = lower_bound(begin(lis), end(lis), key);
		if (*pos == INF) len++;
		*pos = key;
		ans[i] = {pos - begin(lis), key};
	}
    // LIS를 출력하기 위한 tracing 및 스택 push
	stack<int> stk;
	for (int i = N - 1; i >= 0; --i) 
		if (ans[i].first == len - 1) stk.push(ans[i].second), len--;
	
	cout << stk.size() << "\n";
	while (!stk.empty()) {
		cout << stk.top() << " ";
		stk.pop();
	}
}

소스코드 링크

결과