[백준][C++] 8983: 사냥꾼

문제

풀이

이분 탐색을 사용한다. 최악의 경우는 각 동물이 모든 사로에 대해 사냥이 가능한지 검사하는 것으로 O(N * M)으로 100억번의 탐색이 이루어져 시간초과이다. N이나 M 중 하나를 log로 바꿔야 한다. 

• 각 동물마다 이분 탐색으로 해당 사대에서 사냥 가능한지 검사한다. 
• 시간 복잡도가 O(N * log M)으로 줄어든다. 
• 동물이 mid 사대의 왼쪽에 있다면 end를 감소시키고, 오른쪽에 있다면 start를 증가한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> shoots;
vector<pair<int, int>> animals;

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

    int M, N, L;
    cin >> M >> N >> L;

    for (int i = 0; i < M; ++i)
    {
        int temp;
        cin >> temp;
        shoots.push_back(temp);
    }

    for (int i = 0; i < N; ++i)
    {
        int x;
        int y;
        cin >> x >> y;
        animals.push_back(make_pair(x, y));
    }

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

    // 각 동물마다 어느 위치의 사대에서 사냥이 가능한지 이분 탐색
    int answer = 0;
    for (int i = 0; i < N; ++i)
    {
        int start = 0;
        int end = M - 1;
        while (start <= end)
        {
            int mid = (start + end) / 2;

            // mid 사대에서 사냥 가능인지 검사
            int dist = abs(animals[i].first - shoots[mid]) + animals[i].second;
            if (dist <= L)
            {
                answer++;
                break;
            }

            // 동물이 mid 사대의 왼쪽에 있다면 end를 감소
            // 오른쪽에 있다면 start를 증가
            if (animals[i].first < shoots[mid])
            {
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
    }

    cout << answer;

    return 0;
}