백준15922 아우으 우아으이야!!

작성일 | In

문제 링크

  • http://icpc.me/15922

문제 출처

  • 제2회 천하제일 코딩대회 본선 G번

사용 알고리즘

  • lower bound
  • line sweeping

시간복잡도

  • O(n log n)

풀이

이 문제가 처음으로 푼 라인 스위핑 문제였습니다. 대회 당시에 어떤 생각으로 해결했는지의 과정을 서술하도록 하겠습니다.

이 문제를 처음 봤을 때, 처음에는 Naive하게 배열을 채우려고 생각을 했지만 입력의 범위가 너무 컸기 때문에 포기했습니다.
입력의 범위가 10억 단위이므로 log 복잡도가 나와야 한다는 것을 인지하고 이진 탐색을 떠올렸습니다.
선분끼리 겹치는 구간이 있으면 두 선분을 합쳐주는 방식이 떠올랐고, 바로 세부적인 로직을 구상하기 시작했습니다.
A라는 선분의 끝 좌표보다 B라는 선분의 시작 좌표가 앞에 있다면 겹치는 구간이 있다는 것을 의미하므로 lower_bound를 이용해 구현했습니다.
선분을 삽입할 때마다 이진 탐색을 하고, i번째 선분을 삽입하는 경우에 이진탐색은 대락 O(log i)번 연산을 수행합니다.
O(log(n!))은 O(n log n)이므로 최종 시간 복잡도는 O(n log n)이 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

vector<p> arr;
int n;

int low(int num){
    int front = 0, rear = arr.size()-1;  
    if(arr.size() == 0 || arr[arr.size()-1].second < num) return n+1;
    while(rear > front){
        int mid = (front+rear)/2;
        if(arr[mid].second >= num) rear = mid;
        else front = mid+1;
    }
    return rear;
}

int main(){
	int ans = 0;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		int idx = low(x);

		if(idx > n || idx == -1){
			arr.push_back(make_pair(x, y));
		}
		else{
			arr[idx].second = max(arr[idx].second, y);
		}

	}

	for(int i=0; i<arr.size(); i++){
		ans += (arr[i].second - arr[i].first);
	}
	printf("%d", ans);
}