[백준OJ] 8983번 사냥꾼

www.acmicpc.net/problem/8983

8983번: 사냥꾼

---

 

-풀이-

1. 사대들을 입력받고 정렬을 해준다.

2. 입력받는 동물의 x,y좌표를 입력받은 뒤, 이 동물의 x좌표와 같거나, 같지않다면 x보다 큰 값중 가장 작은 값의 인덱스를 구해준다.(lower_bound) 

3. 해당 사대와의 거리를 구해주어 l보다 작다면 cnt를 1 더해준다.

4. 3번이 안되는 경우중, 3번의 인덱스보다 1작은 위치에 있는 사대와도 비교를 해준다.

 

4번이 왜 그러냐면, lower_bound를 통해 얻은 사대를 b사대라고 하면, (b-1).x<= x <= (b.x) 가 되기때문에, 양 사이드를 모두 비교해 주는 것이다.

 

-시간 복잡도- 

처음 사대를 입력받고, 정렬하는데 O(MlogM)의 시간이 걸린다.

아래 로직을 구하는것은 M에대한 lower_bound를 N번 수행하므로 O(NlogM)이 된다.

M과 N의 최댓값이 똑같으므로 수행시간은 O(NlogN)이 된다.

 

-코드-

 

#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 (abs(M[ind] - x) + y <= l) cnt++;
		else if (ind - 1 >= 0 && abs(M[ind - 1] - x) + y <= l) cnt++;
	}
	cout << cnt;
}