[8983] 사냥꾼

문제 출처 : https://www.acmicpc.net/problem/8983

분류 : 이분탐색

백준 8983 사냥꾼

O(n*n)을 O(nlogn)으로 줄이기

---

구현 포인트

1) 1초안에 돌아가야 하므로 O(nlogn) 만에 해결해야 한다.

2) 이를 위해 이분 탐색을 써야 한다.

3) 값의 범위는 int내에서 해결가능 함을 다시 상기시키자.
(항상 값의 범위를 체크하여 자료형을 결정하는 것이 중요하다.)

이 문제가 정답률이 낮은 이유는 아마 시간초과 때문일 것이다.

사로에 대해 모든 동물들을 비교하게 되면 당연히 O(NM)시간이 걸리고, 이는 1초안에 끝나지 않는다.

둘 중 하나를 fix해놓고 나머지 하나를 log시간안에 해결해야 시간초과가 나지 않음을 알 수 있다.

1) 사로를 fixed할 경우

이 경우 한 사로에 대해 사냥이 가능한 동물을 찾는 방식인데, 생각보다 log시간안에 해결하기 쉽지가 않다.

따라서 2)번으로 생각을 넘기자.

2) 동물을 fixed할 경우

이 경우 동물에 좌표에 따라 L값을 이용하면 사냥 가능한 사로의 범위를 알 수 있다.

예를 들어 L=4이고, 동물이 (7,2)에 있다면 동물을 사냥할 수 있는 사로의 범위는 5~9까지 일 것이다.

(왜 이렇게 되는지는 생각해 보자!)

따라서 이 범위에 맞는 사로가 있는지 이분탐색을 이용하면 log시간안에 해결이 가능하다.

(여기서 만약 사로의 범위의 값 하나하나마다 STL에 있는 binary_search 탐색을 돌리면 시간초과가 난다...

당연하게도 사로의 범위는 매우 커질 수 있으므로.. 근데 난 처음에 이렇게 했었다.. 멍청한듯;;)

그렇다면 O(NlogM) 이 되어 1초안에 해결이 가능하다.

코드는 아래와 같다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
    int M, N, L, x, y, cnt=0;
    vector<int> m;
    scanf("%d %d %d", &M, &N, &L);
    for (int i = 0; i < M; i++) {
        int tmp;
        scanf("%d", &tmp);
        m.push_back(tmp);
    }
    sort(m.begin(), m.end());
    for (int i = 0; i < N; i++){
        scanf("%d %d", &x, &y);
        if (y > L) continue;
        int upper = x+L-y, lower = x+y-L, low = 0, high = m.size()-1; // x+=r에 사로가 있으면 됨
        while (low<=high) {
            int mid = (low + high) / 2;
            if (lower <= m[mid] && m[mid] <= upper) {
                cnt++;
                break;
            }
            else if (m[mid] < lower) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
    }
    printf("%d\n", cnt);
}