[백준 8983] 사냥꾼 (C++)

문제 링크: www.acmicpc.net/problem/8983

8983번: 사냥꾼

1. 주의할 점

- 모두 비교할 경우, 최악의 경우 O(N*M)으로 TLE가 발생한다

- 둘중 하나는 lgN이나 lgM으로 바꿔야 TLE가 발생하지 않는다

- 사대의 X값이 정렬되어 있지 않다. 왜?

 

2. 구현

- 입력 받은 사대 Arr[]를 오름차순으로 정렬한다

- 동물들의 위치를 X[], Y[]에 할당 받는다

- 각 동물을 기점으로 사대까지의 거리가 Len보다 작거나 같다면, Result++하고 다음 동물로 넘어간다

- 만약 거리가 Len보다 크다면, 동물기준으로 사대가 우측이면(사대x > 동물x) R = Mid-1로 설정하여 더 왼쪽에 위치한 사대에서 다시 검사할 수 있도록 한다. 반대로, 동물기준으로 사대가 좌측이면(사대x < 동물x) L = Mid+1로 설정하여 더 오른쪽에 위한 사대에서 다시 검사한다

 

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int x[100001];
int y[100001];
int arr[100000];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,animal,len;
    cin>>num>>animal>>len;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    sort(arr,arr+num);
    for(int i=0;i<animal;i++)
        cin>>x[i]>>y[i];
    int result=0;
    for(int k=0;k<animal;k++){
        int l=0,r=num-1,mid;
        while(l<=r){
            mid = l + (r-l)/2;
            int cal = abs(arr[mid]-x[k])+y[k];
            if(cal<=len){
                result++;
                break;
            }
            else{
                if(x[k] >= arr[mid])
                    l = mid+1;
                else r = mid-1;
            }
        }
    }
    cout << result;
    return 0;
}