반응형
알고리즘 종류
- 자료구조
사고 과정
- 현재 시점을 기준으로 다음에 들어올 시작점이 현재 시점 이하이면서 최대 끝지점을 찾으면 된다. 아래 예시를 보자.
- m=10이고 7개의 선분들이 있다. 그려보면 아래와 같다.
1. 현재 시점 0을 기준으로 0이하인 시작점을 가지는 선분들은 [0, 1]과 [0, 5]이다. 이중에서 가장 큰 끝지점을 갖는 것은 [0, 5]이다. 시작점을 0에서 5로 바꿔준다.
1-1. 선분[2, 4]는? 최대 끝지점이 5로 정해지고 선분 [2, 4]가 들어왔다. 최대 끝지점이 5보다 작으므로 무시한다.
2. 현재 시점 5를 기준으로 5이하인 시작점을 가지는 선분들은 [3, 6], [4, 8]이다. 이중에서 가장 큰 지점을 가진 선분은 [4, 8]이다. 시작점을 5에서 8로 바꿔준다.
2-1. 선분 [7, 8]도 마차간지로 무시하고 넘어간다.
3. 현재 시점 8을 기준으로 8이하인 시작점을 가지는 선분은 [7, 10]이다. 목표지점 10에 도달했으므로 선분 [0, 10]을 3개의 선분으로 덮을 수 있다.
구현(C++)
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int> > v;
int m;
int answer=0;
bool cmp(pair<int,int> a, pair<int,int> b){
if(a.first == b.first){
return a.second < b.second;
}
return a.first < b.first;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m;
int l, r;
while(true){
cin >> l >> r;
// 시작과 끝의 조건을 절대값으로 안내되어서 아래와 같이 조정이 필요
if(l>r){
int tmp = l;
l = r;
r = tmp;
}
if(l==0 && r==0) break;
if(r<0 || l>m || l==r) continue;
v.push_back({l, r});
}
// 시작점 오름차순, 끝점 오름차순
sort(v.begin(), v.end(), cmp);
int cur = 0;
int idx = 0;
while(true){
int maxNum = -1;
for(; idx<v.size(); idx++){
if(v[idx].first <= cur){ // 다음에 들어오는 값이 현재 지점 이하인가
if(v[idx].second > maxNum) // 저장된 최대 끝지점 보다 큰 가?
maxNum = v[idx].second;
}
else break;
}
// 다음에 들어오는 시작점이 현재 시작점을 포함하지 못하므로 선분을 덮을 수 없음
if(maxNum == -1){
cout << "0" << endl;
break;
}
answer ++;
if(maxNum >= m){
cout << answer << endl;
break;
}
// 시작점을 최대 끝지점으로 변경
cur = maxNum;
}
}
|
cs |
시행착오
- 라인 스위핑 문제일 것 같아서 우선순위 큐를 사용하려고 시도했다. 그런데 막상 관찰해보니 현재시점을 포함하는 선분들 중에 오른쪽 최대값을 찾으면 될 것 같았다. 더 가볍게 풀기 위해서 많은 문제를 생각해보면서 풀어야 겠다.
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
[백준][C++] 5427 불 (0) | 2021.03.23 |
---|---|
[백준][C++] 17836 공주님을 구해라! (0) | 2021.03.23 |
[백준][C++] 18809 gaaaaaaaaaarden (0) | 2021.03.20 |
[백준][C++] 10217 KCM Travel (0) | 2021.03.19 |
[백준][C++] 9370 미확인 도착지 (0) | 2021.03.18 |