BOJ : https://www.acmicpc.net/problem/2568
2568번: 전깃줄 - 2
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
www.acmicpc.net
문제 해결을 위한 알고리즘 : lis
2007년도 지역본선 중등부3번 문제
가장 긴 증가하는 부분수열4 : https://junho0956.tistory.com/9?category=825556
이 문제에서 언급했듯이 lis 알고리즘의 문제점은 lis 배열의 정확한 값을 찾을 수 없다는 것이다.
그러므로 이 문제를 해결하기 위해서는 lis 알고리즘 뿐만 아니라 정확한 값을 찾아가는 추적 알고리즘이 필요하다.
lis 알고리즘을 사용하면 사용한 전깃줄에 대한 정보를 가지게 되므로,
사용하지 않은 전깃줄을 출력하기 위해서 bool의 visit 배열을 사용하였다.
방식은 일단 먼저 입력되는 전깃줄은 전부 true를 시킨 후에
lis 추적 알고리즘으로 사용된 전깃줄을 다시 false 시키면
결국 남아있게 되는 visit 배열의 true 값을 가진 인덱스가 사용하지 않은 전깃줄이 되게 된다.
|
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
|
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int> > arr;
vector<pair<int, int> > v;
bool visit[500001];
int lis[500001];
int n, f, s, cnt, L;
int _lower_bound(int start, int end, int key) {
int mid;
while (start < end) {
mid = (start + end) / 2;
if (lis[mid] < key)
start = mid + 1;
else
end = mid;
}
return end + 1;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &f, &s);
v.push_back(make_pair(f, s));
visit[f] = true;
}
sort(v.begin(), v.end());
lis[0] = v[0].second;
arr.push_back({ 0,v[0].first });
for (int i = 1; i < n; i++) {
if (lis[L] < v[i].second) {
lis[++L] = v[i].second;
arr.push_back({ L,v[i].first });
}
else {
int ans = _lower_bound(0, L, v[i].second);
lis[ans - 1] = v[i].second;
arr.push_back({ ans - 1, v[i].first });
cnt++;
}
}
for (int i = arr.size(); i >= 0; i--) {
if (arr[i - 1].first == L) {
L--, visit[arr[i - 1].second] = false;
}
if (L == -1) break;
}
printf("%d\n", cnt);
for (int i = 1; i < 500001; i++) {
if (visit[i] == true)
printf("%d\n", i), cnt--;
if (cnt == 0) break;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
위 소스는 직접 lower_bound를 만들어서 사용한 예제이고 아래는 algorithm 헤더로 함수를 바로 사용해본 소스이다.
|
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
|
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int> > arr;
vector<pair<int, int> > v;
bool visit[500001];
vector<int> lis;
int n, f, s, cnt, L;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &f, &s);
v.push_back(make_pair(f, s));
visit[f] = true;
}
sort(v.begin(), v.end());
lis.push_back(v[0].second);
arr.push_back({ 0,v[0].first});
for (int i = 1; i < n; i++) {
if (lis[L] < v[i].second) {
lis.push_back(v[i].second);
arr.push_back({ ++L,v[i].first });
}
else {
vector<int>::iterator ans = lower_bound(lis.begin(), lis.end(), v[i].second);
int answer = lower_bound(lis.begin(), lis.end(), v[i].second) - lis.begin() + 1;
*ans = v[i].second;
arr.push_back({ answer - 1, v[i].first });
cnt++;
}
}
for (int i = arr.size(); i >= 0; i--) {
if (arr[i - 1].first == L) {
L--, visit[arr[i - 1].second] = false;
}
if (L == -1) break;
}
printf("%d\n", cnt);
for (int i = 1; i < 500001; i++) {
if (visit[i] == true)
printf("%d\n", i), cnt--;
if (cnt == 0) break;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
|
algorithm 헤더에 있는 lower_bound 의 사용법
1. iterator 을 사용하는 경우
auto or iterator x = lower_bound(start iterator, end iterator, key);
iterator을 사용하면 주소를 반환하게 된다.
2. index를 사용하는 경우
int val = lower_bound(start iterator, end iterator, key) - start iterator + 1;
이런식으로 사용하면 찾은 값의 인덱스를 return 값으로 반환하게 된다.
헤더파일을 사용하니 메모리 사용량이 감소하는 것으로 나타났다.
'algorithm > BOJ' 카테고리의 다른 글
| 백준 2623번 - 음악프로그램 Junnnho (0) | 2019.05.15 |
|---|---|
| 백준 : 1516번 - 게임 개발 Junnnho (0) | 2019.05.14 |
| BOJ 2352번 반도체 설계 (0) | 2019.04.08 |
| BOJ 2565번 전깃줄 (0) | 2019.04.08 |
| BOJ 14501번 퇴사 (0) | 2019.04.07 |