티스토리 뷰

알고리즘 관련/BOJ

BOJ)8983 사냥꾼

JASON 자손9319 2017. 1. 15. 18:38

문제: icpc.me/8983


KOI 2013 중,고등부 문제이다.


N마리의 동물들의 위치가 좌표로 주어지고 x축위에 M개의 사대가 존재하는데 이때 모든 사대의 사정거리는 공통적으로 L이다.


각 사대에서 동물들과의 거리는 [abs(x(동물)-x(사로))+y(동물)] 로 계산될 때 사냥 가능한 동물의 수를 출력하는 문제이다.


N과 M이 최대 10만까지 그리고 사정거리와 좌표는 1~ 1억까지 들어온다.


우리는 모든 사대와 각 동물들을 비교할 경우 O(N*M)의 시간 복잡도로 TLE를 보게 된다는 걸 알고 있다.


따라서 최대 NlogN의 알고리즘이 필요하다.


우리는 우선 동물들을 x좌표 기준으로 정렬 ,그리고 사대도 x좌표 기준으로 정렬을 할 것이다.


그 다음 동물들을 볼건데 어떤 동물 A를 사냥 가능한 사대는 여러개가 될 수 있지만 A를 기준으로 왼쪽에서 가장 가까운 사대와 오른쪽에서 가장 가까운 사대


이렇게 두 사대만 확인하면 나머지 사대는 확인하지 않아도 된다는 건 자명하다.


게다가 사대와 동물들을 x좌표 기준으로 정렬을 했으니 A동물을 확인 할때 Vn 사대와 Vn+1 사대를 확인했다면 A이후의 동물들을 확인 할 때도 Vn-1 이하의 사대들은 다시 볼일이 없다는 얘기가 된다.


이를 이용하여 사대와 동물들을 비교하여 답을 확인 할 경우 O(N+M)의 시간복잡도에 확인 가능하다.

전체 시간복잡도는 정렬을 하였기에 O(NlogN+MlogM)이 될 것이다.


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 <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 100000
using namespace std;
int xpos[MAX_N];
pair<intint> a[MAX_N];
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 - && 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\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)7795 먹을 것인가 먹힐 것인가  (0) 2017.01.15
BOJ)3758 KCPC  (0) 2017.01.15
BOJ)8983 사냥꾼  (0) 2017.01.15
BOJ)10277 JuQueen  (0) 2017.01.15
BOJ)2877 4와 7  (0) 2017.01.15
BOJ)2775 부녀회장이 될테야  (0) 2017.01.15
댓글
댓글쓰기 폼