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

8983번 : 사냥꾼

---

문제)

KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자.

 

각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다.

 

사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다.

 

예를 들어, 아래의 그림과 같은 사냥터를 생각해 보자. (사대는 작은 사각형으로, 동물의 위치는 작은 원으로 표시되어 있다.) 사정거리 L이 4라고 하면, 점선으로 표시된 영역은 왼쪽에서 세 번째 사대에서 사냥이 가능한 영역이다.

 

 

사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다.

두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌표 값이 빈칸을 사이에 두고 양의 정수로 주어진다.

 

이후 N개의 각 줄에는 각 동물의 사는 위치를 나타내는 좌표 값이 x-좌표 값, y-좌표 값의 순서로 빈칸을 사이에 두고 양의 정수로 주어진다.

 

사대의 위치가 겹치는 경우는 없으며, 동물들의 위치가 겹치는 경우도 없다. 모든 좌표 값은 1,000,000,000보다 작거나 같은 양의 정수이다.

 

 

 

출력 :

출력은 단 한 줄이며, 잡을 수 있는 동물의 수를 음수가 아닌 정수로 출력한다.

 

 

 

 

 

 

풀이)

완전 탐색 풀이 

먼저 완전 탐색을 이용해 풀어보았는데,

n과 m이 모두 최대 10만이므로 둘중 하나를 최적화할 필요가 있었다.

여기서 사대는 x의 위치만 존재하고, 동물들의 위치는 2차원이었기 때문에 최적화가 힘들것이라고 판단.

사대의 위치를 찾는 것을 최적화하기로 결정했다.

 

// 8983. 사냥꾼
#include <iostream>
#include <vector>
 
using namespace std;
 
int m, n;
long long l;
vector<long long> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n >> l;
 
    vec.resize(m);
    for (long long& ele : vec) cin >> ele;
 
    vector<pair<long long, long long>> animal(n);
 
    long long a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        animal[i].first = a;
        animal[i].second = b;
    }
 
    vector<bool> visited(n, false);
 
    // 모든 사대
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        /// 모든 동물 확인
        for (int j = 0; j < n; j++)
        {
            // 조건에 만족한다면 방문처리도 한다 (조금 최적화)
            if (!visited[j] && (abs(vec[i] - animal[j].first) + animal[j].second) <= l)
            {
                visited[j] = true;
                cnt++;
            }
        }
    }
 
    cout << cnt;
 
    return 0;
}
 

 

이후 동물들을 하나하나 돌면서

해당 동물을 잡을 수 있는 사대를 이진 탐색으로 찾는 방법으로 문제를 풀어주었다.

 

// 8983. 사냥꾼
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int m, n;
long long l;
vector<long long> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> m >> n >> l;
 
    vec.resize(m);
    for (long long& ele : vec) cin >> ele;
    sort(vec.begin(), vec.end());
 
    vector<pair<long long, long long>> animal(n);
 
    long long a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        animal[i].first = a;
        animal[i].second = b;
    }
 
    int cnt = 0;
 
    // 모든 동물들을 기준으로.
    for (int i = 0; i < n; i++)
    {
        int s = 0;
        int e = m - 1;
 
        while (s <= e)
        {
            int mid = (s + e) / 2;
 
            // 해당 사대가 사거리 보다 멀리 있다면
            if (abs(vec[mid] - animal[i].first) + animal[i].second > l)
            {
                // 절댓값을 기준으로 s와 e를 조절하여 사대를 찾는다.
                if (vec[mid] >= animal[i].first) e = mid - 1;
                else s = mid + 1;
            }
            else
            {
                cnt++;
                break;
            }
        }
    }
 
    cout << cnt;
 
 
    return 0;
}

---

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

8983번: 사냥꾼