BOJ : https://www.acmicpc.net/problem/14002
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
lis 알고리즘의 가장 큰 문제점은 길이는 정확하게 알수 있는데,
그 값을 찾아가는 과정을 정확하게 알아내지 못한다는 점이다.
같은 수가 나오거나, 길이는 같은데 다른 값이 갱신된다던가 하는 문제이다.
이 때는, lis배열 뿐만아니라 스택과 값을 저장할 벡터를 추가하여 문제를 해결한다.
벡터는 pair로 입력받아, lis에 추가되는 인덱스와 값을 동시에 넣어준다.
lis의 길이를 찾는 과정이 끝나면,
벡터의 끝부분부터 pair의 lis가 같을때 스택에 추가해주고 erase;
그 다음, 스택에 있는 값을 순서대로 출력해주면 된다.
|
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
|
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int lis, n;
int arr[1001];
int Lis[1001];
vector<pair<int, int> > pii;
stack<int> s;
int lower_bound(int start, int end, int target)
{
int mid;
while (end - start > 0)
{
mid = (start + end) / 2;
if (Lis[mid] < target)
start = mid + 1;
else
end = mid;
}
return end + 1;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &arr[i]);
Lis[0] = arr[0];
pii.push_back(make_pair(0, Lis[0]));
for (int i = 1; i < n; i++) {
if (Lis[lis] < arr[i])
{
Lis[lis + 1] = arr[i];
lis++;
pii.push_back(make_pair(lis, arr[i]));
}
else
{
int ans = lower_bound(0, lis, arr[i]);
Lis[ans - 1] = arr[i];
pii.push_back(make_pair(ans - 1, arr[i]));
}
}
printf("%d\n", lis + 1);
for (int i = pii.size(); i >= 0; i--) {
if (pii[i - 1].first == lis) {
s.push(pii[i - 1].second);
lis--;
}
if (lis == -1) break;
}
while (!s.empty()) {
printf("%d ", s.top()), s.pop();
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
복습 20.02.09
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 1965번 상자넣기 (0) | 2019.04.07 |
|---|---|
| BOJ 1937번 욕심쟁이 판다 (0) | 2019.04.06 |
| BOJ 14003번 가장 긴 증가하는 부분수열5 (0) | 2019.04.06 |
| 가장 긴 증가하는 부분수열3(12738) - Junnnho (0) | 2019.04.06 |
| 가장 긴 증가하는 부분수열2(12015) - Junnnho (0) | 2019.04.06 |