백준8983 사냥꾼

작성일 | In

문제 링크

  • http://icpc.me/8983

문제 출처

  • 2013 전국 본선 중등1, 고등1

사용 알고리즘

  • 스위핑

시간복잡도

  • O(n log n + m log m)

풀이

먼저, 사대의 위치를 입력 받고 x좌표를 기준으로 정렬합니다. 그 후, 동물의 좌표를 입력 받고 x좌표를 기준으로, 같다면 y좌표를 기준으로 정렬합니다.
문제를 본격적으로 해결하기 전에 cal이라는 함수를 하나 만듭시다. 이 함수는 동물과 사대 사이의 거리를 구하는 함수입니다. 이 함수와 l값을 이용하여 특정 동물을 사냥할 수 있는지 판별할 것입니다.

본격적으로 문제를 풀업봅시다. 이미 사대와 동물을 각각 좌표를 기준으로 정렬했기 때문에 스위핑 기법을 이용해 비교적 쉽고 빠르게 해결할 수 있습니다.
for문을 통해 동물을 하나씩 보면서 해당 동물을 사냥할 수 있을지 판단할 것입니다. 설명의 편의를 위해 현재 관찰 중인 동물을 i라고 합시다.
방법은 간단합니다. 먼저 i보다 왼쪽에 있는 사대 중, 동물과 가장 가까운 사대를 선택합니다. 그 사대를 s라고 하겠습니다. s에서 i를 사냥할 수 있다면 정답을 1 증가시켜주면 됩니다.
반대의 경우인 s에서 i를 사냥하지 못하는 경우를 생각해봅시다. s의 다음 사대는 i의 바로 오른쪽에 있는 사대입니다. 그 사대를 t라고 합시다. t에서 i를 사냥할 수 있는지 확인해보고 가능하다면 정답을 1 증가시켜줍니다. 만약 s와 t에서 모두 사냥이 불가능하다면, 모든 사대에서 사냥이 불가능하다는 것을 쉽게 알 수 있습니다.

이미 동물들과 사대 모두 정렬이 되어 있기 때문에 스위핑을 하는데에는 O(n+m)정도만 걸립니다.

전체 코드

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

typedef pair<int, int> p;

int xpos[100100];
p a[100100];
int m, n, l, xidx, res;

int cal(int x, int y, int z) {
    return abs(x - z) + y;
}

int main(){
	scanf("%d %d %d", &m, &n, &l);
	for(int i=0; i<m; i++) scanf("%d", &xpos[i]);
	for(int i=0; i<n; i++) scanf("%d %d", &a[i].first, &a[i].second);
	sort(a, a+n);
	sort(xpos, xpos+m);

	for(int i=0; i<n; i++){
        while(xidx != m-1 && xpos[xidx + 1] < a[i].first){
            xidx++;
        }
        if(cal(a[i].first, a[i].second, xpos[xidx]) <= l){
            res++;
            continue;
        }
        if(xidx != m-1){
            if(cal(a[i].first, a[i].second, xpos[xidx + 1]) <= l){
                res++;
                continue;
            }
        }
    }

	printf("%d", res);
}