[BOJ - 8983] 사냥꾼 (C++)

---

• M (사대의 개수), N (동물의 수), L (사정거리)
  • 대각선은 |xi-aj| + bj 로 계산
  • 가장 가까운 거리는 x좌표가 같다고 가정했을 때 y 좌표의 값
  • 따라서 입력받으면서 처리할 때 y 좌표의 값이 L보다 같다면 조건을 확인하는 부분에서 아예 continue 하도록 작업하자
• 그림을 그린다고 생각해보자

좀 잘그렸는데?

아무튼 사대가  x - (L-y) ~ x + (L-y) 범위 내에 존재한다면 이거는 동물을 사냥할 수 있는 경우다.

• 그래서 이진 탐색의 lower_bound 개념을 통해서 이 문제를 접근하고자 결정했다.
  • 사대의 좌표를 정렬
  • x, y값을 입력받은 뒤 left 보다 크거나 같은 값이 처음으로 나오는 위치를 lower_bound를 통해 찾기
  • 만약 해당 위치가 배열의 끝 (vector로 선언한 경우 .end())이 아니고(&&), 해당 위치에 들어있는 값이 right보다 작거나 같다면 사냥 가능 -> cnt++

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int M, N;
ll L;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> M >> N >> L;

    vector<int> shoot(M);
    for (int i = 0; i < M; i++) cin >> shoot[i];
    sort(shoot.begin(), shoot.end());

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;

        if (y > L) continue;

        ll left = x - (L - y);
        ll right = x + (L - y);

        auto it = lower_bound(shoot.begin(), shoot.end(), left);
        if (it != shoot.end() && *it <= right) cnt++;
    }

    cout << cnt;

    return 0;
}

 

링크

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