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

이 문제는 이분 탐색을 이용해서 푸는 문제이다.

 

사대의 수 M은 [1, 100,000] 이고, 동물의 수 N도 [1, 100,000]이다. 즉, 각 사대나 각 동물에 대해서 모든 동물 혹은 모든 사대를 루프로 검색하는 것은 시간 초과가 난다.

따라서 O(N log N) 이하의 알고리즘을 생각해야 한다.

 

각 사대에 대해 동물을 이분 탐색으로 찾는 것보다는 각 동물에 대해 사대를 이분 탐색으로 찾는 게 더 쉬워보였다.

따라서 사대 배열을 오름차순으로 정렬하고, 각 동물에 대해 루프를 돌며 이분 탐색을 수행한다.

 

이분 탐색 로직의 경우에는 우선 mid를 찾고, 해당 인덱스의 사대에 대해서 거리가 사정거리 이하면 true를 리턴한다.

 

만약 아닐 경우, 사대가 동물보다 오른쪽에 있는 경우에는 왼쪽 사대들을 검색해줘야 한다. 따라서 right = mid - 1을 해준다.

사대가 동물보다 왼쪽에 있는 경우는 오른쪽 사대들을 검색해줘야 하므로 left = mid + 1로 해준다.

만약 사대와 동물의 x좌표가 같다면, 이미 사정거리가 안되는 것이므로 false를 리턴해주면 된다.

 

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

using namespace std;

int M, N, L;

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

int absolute(int num) {
	if (num < 0) {
		return -num;
	}
	return num;
}

bool binarySearch(int animalX, int animalY) {
	int left = 0;
	int right = shoots.size() - 1;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (absolute(shoots[mid] - animalX) + animalY <= L) {
			return true;
		}
		else {
			if (shoots[mid] > animalX) {
				right = mid - 1;
			}
			else if (shoots[mid] < animalX) {
				left = mid + 1;
			}
			else {
				return false;
			}
		}
	}

	return false;
}

int main() {
	cin >> M >> N >> L;

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

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

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;

		animals.push_back({ x, y });
	}

	int answer = 0;
	for (pair<int, int> &animal : animals) {
		int x = animal.first;
		int y = animal.second;

		if (binarySearch(x, y)) {
			answer++;
		}
	}

	cout << answer << '\n';

	return 0;
}