[백준OJ] 8983번 사냥꾼

https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

---

 

 

풀이

1. 먼저 lower_bound(이분탐색) 함수를 사용하기위해서, 입력받은 발사대를 오름차순 정렬을 해준다.

2. 동물을 입력받음과 동시에, 동물의 x좌표와 가까운 발사대를 lower_bound를 통해 찾는다.

3. 해당 발사대와의 거리가 L 이하라면, answer++를 해준다.

4. 해당 발사대와 거리가 멀다면 , 해당 발사대의 이전 발사대를 조사해 L 이하라면 answer++를 해준다.

 

※주의점※

Lower_bound 함수는 해당 배열 혹은 벡터에서 key값과 같은 값을 찾고, 만약 없다면 key값보다 큰 가장 작은 정수를 찾아준다.

따라서 해당 key값이 배열 혹은 벡터의 마지막원소 (제일 큰 원소) 보다 크다면, 배열/벡터의 사이즈+1 을 리턴해주기 때문에, out of index 처리를 잘 해주어야 한다.

 

시간복잡도

발사대를 정렬하는데 O(MlogM)

각 동물의 좌표마다 이분탐색을 하므로, O(NlogM)이 된다.

 

따라서 총 O(NlogN)이 된다. (M의범위 == N의 범위)

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

vector<long long> M;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n, m, l, cnt = 0;
	cin >> m >> n >> l;
	for (long long i = 0; i < m; i++) {
		long long data;
		cin >> data;
		M.push_back(data);
	}
	sort(M.begin(), M.end());
	for (long long i = 0; i < n; i++) {
		long long x, y;
		cin >> x >> y;

		long long ind = lower_bound(M.begin(), M.end(), x) - M.begin();
		if (ind!=m&&abs(M[ind] - x) + y <= l) cnt++;
		else if (ind - 1 >= 0 && abs(M[ind - 1] - x) + y <= l) cnt++;
	}
	cout << cnt;
}