[BOJ 8983] 사냥꾼

BOJ 8983 샤낭꾼

유형

• 이분탐색
• 정렬

풀이

처음 풀이를 생각할 때에는 사대 위치를 기준으로 동물의 좌표와 거리를 판단하여 잡을 수 있는지 확인하려고 하였으나 풀다보니 비효율적이라고 생각이 되었다.

그래서 다시 생각을 해보니 동물의 좌표를 기준으로 사대와 거리를 판단하면 더 빠르게 풀 수 있을 것 같았다.

풀이방법은 사대 위치를 오름차순 정렬한다. 그리고 동물의 좌표를 차례대로 순회하며 동물의 x좌표를 타겟으로 사대 위치들을 이분탐색하면서 가장 가까운 위치에 있는 두개의 사대를 찾아내고 두 사대에서 거리 l 안에 들어오는지 판단하였다.(처음과 끝 사대는 하나의 사대만 판단)

algorithm 라이브러리에서 제공하는 lower_bound 함수를 사용하여 구현하였다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, l;
vector<int> attack(100001);

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> m >> n >> l;
	for (int i = 0; i < m; i++) {
		cin >> attack[i];
	}
	// 사대 위치를 오름차순 정렬
	sort(attack.begin(), attack.begin() + m);

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		// x좌표를 기준으로 가장 가까운 사대를 찾음
		auto iter = lower_bound(attack.begin(), attack.begin() + m, x);
		// 처음이 아니면 이전 인덱스와 비교
		if (iter != attack.begin()) {
			if (abs(*(iter - 1) - x) + y <= l) {
				ans++;
				continue;
			}
		}
		// 끝이 아니면 현재 인덱스와 비교
		if (iter != attack.begin() + m) {
			if (abs(*iter - x) + y <= l) ans++;
		}
	}
	cout << ans;
	
	return 0;
}