[백준] 8983번: 사냥꾼

https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

문제 이해

일단 기본적으로 주어지는 입력 들의 수가 굉장히 크다.

사대가 최대 100,000개이고, 동물의 수가 최대 100,000 이기 때문에, 각 사대 별 동물 탐색, 혹은 동물별 사대 탐색을 하면 100,000 * 100,000 = 10,000,000,000번의 루프이므로 절대 시간 내에 문제를 풀 수 없다.

 

탐색의 시간을 줄이기 위해 Binary Search를 사용한다. 

 

동물 별로, 그 동물을 쏠 수 있는 사대의 범위를 구한다. 

동물의 Y좌표가 L(사정거리)보다 크면 어디서도 쏘지 못한다.

사대 별 사정 범위를 살펴보면 x + y == L 인 곳까지 쏠 수 있다는 것을 알 수 있다.

이걸 반대로 동물 입장에서 생각하면 동물의 x 좌표의 (사정거리 - 동물의 y좌표)만큼의 좌우에 사대가 있으면 잡히는 것이다. 

int left = an[i].x - (L - an[i].y);
int right = an[i].x + (L - an[i].y);

동물을 쏠 수 있는 사대 위치의 범위를 위와 같이 수식으로 정리하고, 이진 탐색으로 해당 범위에 사대가 있는지 확인하면 된다. 

 

작성 코드 (C)

#include <stdio.h>
#include <stdlib.h>

typedef struct pos {
    int y;
    int x;
}POS;

int M; // 사대의 수
int N; // 동물의 수
int L;  // 사정거리
int sa[100000 + 10];   // 사대 위치(x좌표)
POS an[100000 + 10]; // 동물 위치(y, x)

int comp(const void* a, const void* b) {
    int* p = (int*)a;
    int* q = (int*)b;
    return *p - *q;
}

int BS(int s, int e, int ts, int te) {

    int ret = -1;
    int m;
    while (s <= e) {
        m = (s + e) / 2;
        if (sa[m] >= ts && sa[m] <= te) {
            ret = m;
            return ret;
        }
        else if (sa[m] > te) {
            e = m - 1;
        }
        else {
            s = m + 1;
        }
    }
    return ret;
}

int main(void) {
    int cnt = 0;

    // 입력
    scanf("%d %d %d", &M, &N, &L);
    for (int i = 0; i < M; i++) {
        scanf("%d", &sa[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &an[i].x, &an[i].y);
    }

    qsort(sa, M, sizeof(int), comp);

    for (int i = 0; i < N; i++) {
        // 모든 동물에 대해 사격 가능한 사대 위치 파악
        if (an[i].y > L) continue;
        int left = an[i].x - (L - an[i].y);
        int right = an[i].x + (L - an[i].y);
        if (BS(0, M - 1, left, right) != -1) cnt++;
    }

    printf("%d", cnt);
    return 0;
}

 

작성 코드(C++)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int M; // 사대의 수
int N; // 동물의 수
int L;  // 사정거리
vector<int> sa;   // 사대 위치(x좌표)
vector<pair<int, int> > an; // 동물 위치(y, x)

int BS(int s, int e, int ts, int te){
    
    int ret = -1;
    int m;
    while(s<=e){
        m = (s+e)/2;
        if(sa[m] >= ts && sa[m] <= te){
           ret = m;
           return ret;
        }else if(sa[m] > te){
            e = m-1;
        }else{
            s = m+1;
        }
    }
    return ret;
}

int main(void) {
    int cnt = 0;

    // 입력
    scanf("%d %d %d", &M, &N, &L);
    for(int i = 0; i<M; i++){
        int tmp;
        scanf("%d", &tmp);
        sa.push_back(tmp);
    }
    for(int i = 0; i<N; i++){
        int y, x;
        scanf("%d %d", &x, &y);
        an.push_back(make_pair(y, x));
    }

    sort(sa.begin(), sa.end());
    
    
    for(int i = 0; i<N; i++){
        // 모든 동물에 대해 사격 가능한 사대 위치 파악
        if(an[i].first > L) continue;
        int left = an[i].second - (L-an[i].first);
        int right = an[i].second + (L-an[i].first);
        if(BS(0, M-1, left, right)!= -1) cnt++;
    }

    printf("%d", cnt);
    return 0;
}