[Algorithm]Baekjoon 8983번 :: 사냥꾼

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
int m, n, l, animalX, animalY;
int shootingPositions[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> m >> n >> l;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> shootingPositions[i];
    }
 
    sort(shootingPositions, shootingPositions + m);
 
    int answer = 0;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> animalX >> animalY;
 
        if (animalY > l) continue;
 
        int minShootingX = animalX + animalY - l;
        int maxShootingX = animalX - animalY + l;
 
        int left = 0;
        int right = m - 1;
 
        while (left <= right)
        {
            int mid = (left + right) / 2; // 사로의 인덱스
            int shootingX = shootingPositions[mid];
 
            if (shootingX >= minShootingX && shootingX <= maxShootingX)
            {
                ++answer;
                break;
            }
            else if (shootingX < minShootingX)
            {
                left = mid + 1;
            }
            else if (shootingX > maxShootingX)
            {
                right = mid - 1;
            }
        }
    }
 
    cout << answer;
 
}
 
 

 

 

 

꽤나 풀어보길 잘했다고 생각하는 문제. 물론 한번에 풀지는 못했지만...

 

문제에서 요구하는 답은 잡을 수 있는 동물의 수를 구하는 것이다.

근데 동물의 수는 총 10만, 사로의 수도 총 10만

단순계산하면 100억이라, 당연히 타임아웃이다.

 

그러니 다음과 같이 생각해보자.

동물위치값을 고정시키고, 해당 동물위치값을 기준으로 이 동물을 잡을 수 있는 사대의 범위값을 구해보는 것이다.

그리고 해당 사대의범위값에 해당하는 사대의 위치가 실제로 입력값에 있다면, 이 동물은 사냥당할 수 있다고 판당할 수 있을것이다.

 

그리고 이 사대의 범위값에 해당하는 사대의 위치(x값)을 구하기 위해 이분탐색을 사용하는 것이다.

 

사대의범위값 구하는건 직접 생각해보면 감이올건데, 위의 코드보다는 아마 아래의 코드보는게 더 납득이 빠를것이다.

 

int minShootingX = animalX - abs(animalY - l);
int maxShootingX = animalX + abs(animalY - l);

 

동물입장에서는 먼저 X축까지 l값을 이용해서 간 다음, 남은 l값으로왼쪽이나 오른쪽으로 이동하는 느낌이라고 생각하면 된다.

즉 animalY - l값은 동물이 x축까지 걸어간다음 남은 l값이고, 이걸 animalX에서 빼버리면 -X축쪽으로 이동하는거니까 사대의 최소X값이 되는거고 animalX에 더해버리면 +X축쪽으로 이동하는거니까 최대 X값이 되는것이다.

 

이렇게 동물을 사냥할 수 있는 사대의 범위를 구했으니, 입력받은 사대의 위치값들을 오름차순정렬시키후, 인덱스값을 mid값으로해서 이분탐색하면 된다.

 

현재 'mid값인덱스에 해당하는 사대의 위치값'이 '동물의 위치를 기준으로 한 사대의범위'에 해당하면 해당 동물은 사냥이 가능한것이니 ++answer해주고, 다음 동물로 넘어간다.

만약 사대의위치값이 사대의 범위중 최솟값보다 작다면, 범위를 크게 잡아줘야하니 오른쪽으로 옮겨주고 최대값보다 크다면 범위를 작게 잡아줘야하니 왼쪽으로 옮겨주면 된다.