[BOJ] 8983 사냥꾼

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

 

 

문제 풀이:

어떤 동물을 잡을 수 있는지 알기 위해 모든 사대와 거리를 계산하면 총 수행 시간은 O(n*m)으로 시간 초과가 난다.

 

binary search 알고리즘을 이용하면 시간을 줄일 수 있다!

 

1. 사대의 위치를 입력받고 정렬한다.

2. 동물의 위치를 입력받는다.

3. 그 동물과 가장 가까운 곳에 위치한 사대의 위치를 binary search를 이용하여 찾는다.

• lower_bound를 찾은 다음 [해당 index]와 [index-1] 중 동물과 가까운 곳을 뽑아 거리를 계산한다.
• 아래 소스코드에는 lower_bound를 구현하였으나,
  • index = lower_bound(vector.begin(), vector.end(), 동물 위치) - vector.begin();
    • 다음과 같이 라이브러리를 사용할 수 있다.
    • header: <algorithm>
  • lower_bound(): 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치 리턴

4. 그 사대와 거리가 l 이하이면 res++;

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define MAX 1000000000
using namespace std;


typedef long long ll;
typedef pair<ll, ll> P;
ll n, m, l,res;

vector<ll> gun;

// 가장 가까운 사대 찾기 
int func(ll animal) { // x 좌표

	ll l = 0,r=gun.size()-1;
	while (l < r) {
		ll mid = (l + r) >> 1;

		if (gun[mid] < animal) l = mid + 1;
		else r = mid;
	}
    //ll l = lower_bound(gun.begin(), gun.end(), animal)-gun.begin(); 과 동일
    
	if (l > 0) {
		if (abs(animal - gun[l - 1]) < abs(animal - gun[l])) return gun[l - 1];
		else return gun[l];
	}
	else return gun[l];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n >> l;
	for (int i = 0; i < m; i++) {
		ll a;
		cin >> a;
		gun.push_back(a);
	}

	sort(gun.begin(), gun.end());
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		ll p=func(a);
		if (abs(a - p) + b <= l) res++;
	}



	cout <<res << '\n';
	return 0;
}