(골드4)백준 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보다 작거나 같은 양의 정수이다.

출력

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

---

핵심

1. x좌표 m개를 입력 받는다.

2. (x, y)좌표 n개를 입력 받는다.

3. m개의 x좌표에서 최대 l 만큼 이동하여 도달할 수 있는 (x,y)좌표의 수를 출력한다.

(대각선 좌표는 [x-m]+y로 계산)

---

내가 작성한 코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int m, n, l;
    cin >> m >> n >> l;

    vector<int> m_list;
    for (int i = 0; i < m; i++)
    {
        int temp;
        cin >> temp;
        m_list.push_back(temp);
    }

    // 사대 정렬
    sort(m_list.begin(), m_list.end());

    vector<pair<int, int>> animal;

    // 동물 좌표 입력
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        animal.push_back({x, y});
    }

    sort(animal.begin(), animal.end());

    int idx = 0;
    int cnt = 0;
    for (auto ele : animal)
    {
        // 동물 좌표 정렬하고 시작 값을 기억해두면 선형으로 될거 같은데?
        for (int i = idx; i < m - 1; i++)
        {
            // 동물로부터 가장 가까운 사수를 탐색하여 idx에 저장
            if (abs(m_list[i] - ele.first) < abs(m_list[i + 1] - ele.first))
            {
                idx = i;
                break;
            }
        }

        // 위 반복문은 마지막 사수가 가까운 경우를 체크하지 못함, 예외 처리
        if (abs(m_list[idx] - ele.first) > abs(m_list[idx + 1] - ele.first))
        {
            idx = m - 1;
        }

        if (abs(m_list[idx] - ele.first) + ele.second <= l)
        {
            cnt++;
            // cout << m_list[idx] << "\n";
            // cout << ele.first << " " << ele.second << "\n";
        }
    }

    cout << cnt;

    return 0;
}

---

풀이

위 문제는 아마도

1. 사수의 x값을 정렬한 뒤, 

2. 모든 동물의 x좌표에 대해 가장 가까이 있는 사수의 위치를 이분 탐색으로 찾은 뒤

3. 해당 사수로 부터 동물의 좌표까지의 거리를 계산하는 방식

으로 풀이하는 문제였던거 같다. (이분 탐색 카테고리에 있었으니)

 

하지만 동물의 좌표까지 x를 기준으로 정렬하고 사수의 위치 인덱스를 기억하면 더 효율적으로 풀 수 있을거 같았다.

1. 사수의 x값을 정렬한 뒤,

2. 모든 동물의 좌표를 정렬한 뒤,

3. 동물의 x좌표로 부터 가장 가까운 사수의 x좌표를 선형 탐색한다.

 

이분 탐색을 사용한 시간 복잡도는 O(N*logM)이지만.

정렬 후 값을 기억한 선형탐색은 O(N+M)으로 계산된다.

 

1트에 풀었다.

GOOOOOOD.