[8983번] 사냥꾼

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. map STL

2. lower_bound

이 문제의 핵심은 다음과 같다.

어떤 동물의 x좌표가 a1이라 하고

그 동물보다 a1 좌표 이상인 것 중 가장 가까운 사대 g2와 그 사대 바로 이전의 사대 g1이 3개의 좌표가 있다면

어떤 동물 x는 무조건 g1,g2에서 잡히냐 안잡히냐 둘중 하나이다.

a1이 다음과 같은 위치에 있었을 경우, g2가 아닌 g0와 g1을 비교해야 한다.

이 그림에 대해서는 조금있다 나올 g1 < a1 < g2의 그림을 확인해보자.

이 그림의 경우 a1의 lower_bound는 g2이다.

따라서 g2의 바로 전 사대는 g1이 되고, a1은 결국 g1과 g2중 하나에 걸리게 되어있다는 의미이다.

a1이 저렇게 있다면 lower_bound는 g2이다. 그 바로전 사대는 g1이 될 것이고 

결국 g1 혹은 g2 둘중 하나에 걸리지 않으면 g2 다음 사대 g3에서는 당연히 해당 사대 범위밖에 있게된다.

이런식으로 문제를 접근하여 map과 map에 존재하는 lower_bound함수를 이용하여 문제를 해결 할 수 있다. 

[참고] 코드에서 이 문제는 동물은 사실 map에 넣지 않고 생각해도 된다.

사대만 정렬되어있다면 동물을 lower_bound를 찍어 사대를 찾으면 되기 때문이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
 
using namespace std;
 
map<int, int> gun;
map<pair<int, int>, int> animal;
map<pair<int, int>, int> mp;
 
int main()
{
    int m, n, l;
 
    scanf("%d %d %d", &m, &n, &l);
 
    for (int i = 0; i < m; i++)
    {
        int val;
        scanf("%d", &val);
        gun[val] = 1;
    }
    
    for (int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        animal[{ x,y }] = 1;
    }
    
    bool chk;
    int cnt = 0;
    for (auto ait = animal.begin(); ait != animal.end(); ait++)
    {
        chk = false;
        // 동물 x좌표 이상인 것 중 가장 가까운 것
        auto tmp2 = gun.lower_bound(ait->first.first);
        
        if (tmp2 != gun.begin())
        {
            tmp2--;
            chk = true;
        }
 
        auto tmp1 = tmp2;
 
        if(chk)
            tmp2++;
 
        // 어짜피 그 동물은 x1, x2 사대 사이에서 잡히거나 잡히지 않거나이다.
        int gunx1 = tmp1->first;
        int gunx2 = tmp2->first;
        int anix = ait->first.first;
        int aniy = ait->first.second;
 
        if (abs(gunx1 - anix) + aniy <= l)
            cnt++;
 
        else if (abs(gunx2 - anix) + aniy <= l)
            cnt++;
    }
 
    printf("%d", cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>