백준 8983번 사냥꾼 C++

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

8983번: 사냥꾼

 

 문제 풀이

 이 문제를 처음 도전할 때는 모든 사대에 대해서 잡을 수 있는 동물들을 카운트 해주는 Brute Force 방법을 쓸 수 있다(시간복잡도 O(MN). 그렇게 하면 M과 N이 100000이하이기 때문에 시간초과가 날 것이다. 그래서 다른 방법을 생각해보면 이부 분탐색이 떠오른다. 모든 동물에 대해서 조건을 만족하는 사대를 이분탐색으로 찾아주면 시간복잡도 O(MlogN)으로 시간초과가 나지 않을 것이다. 조건은 사대와 동물 사이 거리가 L보다 작은 것이므로 아래와 같이 정리할 수 있다.

|x - a| + b ≤ L ⇔ |x - a| ≤ L - b
⇔ b - L ≤ x - a ≤ L - b
⇔ a + b - L ≤ x ≤ a - b + L

 

각각의 동물의 좌표 (a,b)에 대해 위의 조건을 만족하는 사대의 x좌표가 존재하기만 하면 그 동물은 잡을 수 있는 동물이다.

 

시행 착오

 가장 처음에는 시간복잡도를 고려하지 않고 무작정 O(n^2)이 걸리는 Brute Force로 코드를 짰는데 60점이 나와서 조건을 다시 봤다... 이후에는 이분탐색 생각을 하긴 했는데 다른 조건으로 이분탐색을 해서 한참 해맸다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int x,y,M,N,L,n=0,X[100000];
    cin>>M>>N>>L;
    
    for(int i=0;i<M;i++)
    {
        cin>>X[i];
    }
    sort(X,X+M);
    
    for(int i=1;i<=N;i++)
    {
        cin>>x>>y;
        if(y>L)
        {
            continue;
        }
        
        int lower=x+y-L,upper=L+x-y,r=M-1,l=0,m;
        while(l<=r)
        {
            m = (r+l)/2;
            if(X[m]>=lower&&X[m]<=upper)
            {
                n++;
                break;
            }
            else if(X[m]<lower)
            {
                l = m + 1;
            }
            else
            {
                r = m-1;
            }
        }
    }
    cout<<n;
}