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

문제 링크

8983번: 사냥꾼

문제 요약

N마리의 동물과 M개의 사대가 있다. 사냥꾼은 각 사대에서 사격이 가능하다. 사대는 Y좌표가 0이고, X좌표만 존재한다. 사냥꾼의 총의 사거리는 L이다. N마리의 동물에 대한 X, Y좌표가 주어질 때, 사냥꾼이 사냥할 수 있는 동물의 수를 구해야 한다.

접근 방법

M과 N이 각각 최대 10만이고 이 둘의 곱은 100억이기 때문에 $O(N \times M)$ 풀이는 통과할 수 없습니다. 따라서 이분탐색을 이용해야 합니다.

문제에 나와 있듯이 동물의 좌표 $(a_j, b_j)$와 사대의 위치 $x_i$ 사이의 거리는 $|x_i - a_j| + b_j$로 구할 수 있습니다. 이 값이 총의 사정거리 $L$보다 작거나 같으면 됩니다. 따라서 $L \geq |x_i - a_j| + b_j$인 $x_i$가 존재하기만 하면 $(a_j, b_j)$ 위치의 동물은 사냥할 수 있습니다.

절댓값을 적절하게 처리해주면, 이분탐색을 하면서 $a_j - L + b_j$와 $a_j + L - b_j$ 사이에 있는 사대를 찾아주면 됩니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int main(void)
{
	FASTIO;

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

	vector<int> v(m);
	for (int i = 0; i < m; i++)
		cin >> v[i];

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

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

		if (y > l)
			continue;

		int start = 0, end = m - 1, left = x - l + y;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			
			if (abs(v[mid] - x) + y <= l)
			{
				cnt++;
				break;
			}
			else if (v[mid] < left)
				start = mid + 1;
			else
				end = mid - 1;
		}
	}

	cout << cnt << endl;
	return 0;
}