BOJ 8983 - 사냥꾼

www.acmicpc.net/problem/8983

8983번: 사냥꾼

 

이 문제는 이분탐색을 써야 풀 수 있다.

최댓값이 십만이기 때문에 사대의 위치와 동물의 위치를 이중 포문으로 탐색하면 시간초과가 나기 때문이다.

사대의 위치를 기준으로 탐색하기보다는, 동물의 위치를 기준으로 해당 동물과 가까운 사대를 찾는 방식으로 풀어야 더 수월하게 풀 수 있다. 

 

사대의 위치를 먼저 배열에 다 받아둔뒤, 오름차순으로 정렬시키고,

동물의 좌표를 받을때 마다 이분탐색을 수행한다. 

동물과 사대가 사정거리내에 있는지 판별하는 식은 문제에서 제시한대로 

| x - a | + b <= L 이다 (a, b 는 동물의 좌표, x 는 사대의 좌표, L 은 총의 사정거리)

 

문제에서는 1사분면만 다루므로, L - b 가 음수라면 |x - a| 도 음수가 되야해서, 조건에 맞지 않으므로 패스해주고

|x - a| <= L - b 가 가능한 것은 x - a <= L - b 일때, a - x <= L - b 일때 이다

이를 정리하면 a - (L - b) <= x <= a + (L - b) 가 된다.

그러므로 이에 맞게 이분탐색을 수행하려면

(upper_bound(a + (L - b)) - lower_bound(a - (L - b))) >0 일때만 조건에 부합하는 대상이 있는 것이므로, 이때 답을 카운팅한다.

 

 

- c++

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 
using namespace std;
 
int M, N, L, answer;
vector<int> lanes; 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> M >> N >> L;
    
    for (int i = 0; i < M; ++i) {
        int lane;
        cin >> lane;
        lanes.push_back(lane);
    }
    
    sort(lanes.begin(), lanes.end());
    
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        int temp = L - b; // |x - a| + b <= L (사격 가능한 거리)
        if (temp < 0) continue; // temp 가 음수면 |x - a| 도 음수임 (문제에선 1사분면만 다룸)
        if (upper_bound(lanes.begin(), lanes.end(), a + temp) - lower_bound(lanes.begin(), lanes.end(), a - temp) > 0)
            answer++;
    }
    
    cout << answer;
    
    return 0;
}

 

 

 

 

 

- 참고)

jackpot53.tistory.com/33

이진탐색-상/하한선((lower bound,upper bound)