문제
가장 긴 증가하는 부분 수열의 해를 직접 구하는 문제.
풀이: 크기 구하기
먼저 크기를 구해보자
O(NlogN)으로 풀기위해서
cached라는 vector 타입을 선언하였고
이 배열안에 수열의 원소를 앞에서 부터 cached에 집어넣었다.
이 때 집어넣은 원소는 cached에서 어느 위치에 올 수 있는지 검사한다.
이 위치는 현재 집어넣을 원소보다 큰 첫번째 원소이다.
이렇게 값을 업데이트해주어도 상관이 없는 이유는
- 추가하려는 원소는 오직 자기 자신보다 큰 값이 있는가만 생각하기 때문이며
- 업데이트 되어도 업데이트 된 값으로 다시 그 길이 만큼 수열을 만들 수 있기 때문이다.
풀이: 해 구하기
문제는 해를 직접 구해야한다는 것이다.
이를 구하기 위해 cached를 이차원 벡터로 변경하였고, 원래 수열의 인덱스를 포함시키기 위해 pair 자료구조를 이용하였다.
이렇게 하면 맨 끝에서부터 이진 탐색으로 뒤의 원소보다 인덱스가 작은것을 찾을 수 있다.
즉, 뒤에서부터 답을 추적할 수 있다는 것이다.
- 해를 구하는 track 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void track(int idx, int before)
{
if (idx == -1)
{
return;
}
auto compare = [](const pii &a, const pii &b)
{
return a.second < b.second;
};
vector<pii> &vp = cached[idx];
auto it = lower_bound(vp.begin(), vp.end(), pii(0, before), compare);
if (it != vp.begin())
{
it--;
}
track(idx - 1, it->second);
cout << it->first << " ";
}
- 이차원 벡터의 lower_bound를 다음과 같이 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int my_lower_bound(vector<vector<pii>> &vvp, int low, int high, int X)
{
if (low > high)
{
return low;
}
int mid = low + (high - low) / 2;
if (mid >= vvp.size() || vvp[mid].back().first >= X)
{
return my_lower_bound(vvp, low, mid - 1, X);
}
return my_lower_bound(vvp, mid + 1, high, X);
}
- cached는 아래의 push 함수를 통해 업데이트 시킬 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void push(int item, int idx)
{
if (cached.empty())
{
cached.push_back(vector<pii>(1, {item, idx}));
}
else
{
int loidx = my_lower_bound(cached, 0, cached.size(), item);
if (loidx == cached.size())
{
cached.push_back(vector<pii>(1, {item, idx}));
}
else
{
cached[loidx].push_back({item, idx});
}
}
}
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// start : 2022-01-04 15:36:45
#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <tuple>
#include <algorithm>
#include <vector>
#include <iterator>
#include <functional>
using namespace std;
using pii = pair<int, int>;
// start : 2022-01-04 15:36:45
vector<vector<pii>> cached;
int my_lower_bound(vector<vector<pii>> &vvp, int low,
int high, int X)
{
if (low > high)
{
return low;
}
int mid = low + (high - low) / 2;
if (mid >= vvp.size() || vvp[mid].back().first >= X)
{
return my_lower_bound(vvp, low, mid - 1, X);
}
return my_lower_bound(vvp, mid + 1, high, X);
}
void push(int item, int idx)
{
if (cached.empty())
{
cached.push_back(vector<pii>(1, {item, idx}));
}
else
{
int loidx = my_lower_bound(cached, 0, cached.size(), item);
if (loidx == cached.size())
{
cached.push_back(vector<pii>(1, {item, idx}));
}
else
{
cached[loidx].push_back({item, idx});
}
}
}
void track(int idx, int before)
{
if (idx == -1)
{
return;
}
auto compare = [](const pii &a, const pii &b)
{
return a.second < b.second;
};
vector<pii> &vp = cached[idx];
auto it = lower_bound(vp.begin(), vp.end(), pii(0, before), compare);
if (it != vp.begin())
{
it--;
}
track(idx - 1, it->second);
cout << it->first << " ";
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
int a;
cin >> a;
push(a, i);
}
cout << cached.size() << "\n";
track(cached.size() - 1, N);
}