O(NlogN) LIS를 구현하는 방법은 이전에 알아봤다. 길이 i를 만드는 수열의 최소 마지막 숫자를 v[i]에 저장한다.
그럼 이제 그 수열을 어떻게 출력하는게 좋을까?
그냥 v에 저장된거 순서대로 출력하면 당연히 틀린다. 10 20 30 11이 주어지면 11 20 30이 출력될 것이다.
v[i]가 갱신될때마다 이전 값을 기록하면 그걸 계속 따라가면서 증가 부분 수열을 출력할 수 있다.
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[1000001];
int arr2[1000001]; // 증가 부분 수열에서 이전 값의 인덱스
vector<int> v; // 값
vector<int> v2; // 자기 인덱스
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
v.push_back(-1000000001);
v2.push_back(-1);
for (int i = 0; i < N; i++) {
cin >> arr[i];
auto iter = lower_bound(v.begin(), v.end(), arr[i]);
if (iter == v.end()) {
v.push_back(arr[i]);
v2.push_back(i);
arr2[i] = *(v2.end()-2);
}
else {
*iter = arr[i];
v2[iter-v.begin()] = i;
arr2[i] = v2[iter-v.begin()-1];
}
}
cout << v.size()-1 << '\n';
vector<int> v3;
int idx = *(v2.end()-1);
while (idx != -1) {
v3.push_back(arr[idx]);
idx = arr2[idx];
}
for (auto iter = v3.rbegin(); iter != v3.rend(); iter++) {
cout << *iter <<' ';
}
return 0;
}
얘도 탑다운으로 풀라면 개어려움.
이거 풀었더니 백준 플레티넘이 되었다. 9월부터 다시 시작했으니까 골드에서 두세달정도 걸린듯?
근데 아직 전역할라면 1년남음 아 ㅋㅋ
나도 데려가..