백준 8983 사냥꾼

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

아이디어

• 접근 1. 모든 사대 위치에서 동물의 위치를 비교
  • 모든 사대위치 : O(M)
  • 동물 위치 : O(N)
  • 총합 : O(NM) > 시간초과
• 접근 2. 모든 동물에서 사정거리 안에 있는 사대가 있는지 확인
  • 사정거리 - 동물 y좌표 안에 사대가 있으면 됨
  • 사대를 정렬해서, 그 사이에 있는 값을 찾음
  • 사이에 있는 값을 찾는 방법
    • A와 B 사이의 값을 찾는다고 했을떄
    • A와 같거나 큰값을 찾은다음에
    • B값보다 작은지 확인

시간복잡도 계산

• 사대 정렬 : MlgM
• 모든 동물 : N
• 사대 이진탐색 : lgM
• 총합 : MlgM + NlgM = O(NlgN) > 가능

자료구조

• 동물 위치 : pair<int, int> []
  • y,x 좌표 최대 1e9 > INT 가능
• 사대 위치 : int[]
  • x 좌표 최대 1e9 > INT 가능
• 잡을수 있는 동물수 cnt
  • 최대 1e5 > INT 가능

코드(C++)

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> pi2;
 
pi2 animal[100010];
int gun[100010];
int N,M,L;
 
bool binsearch(int st, int en, int lx, int rx) {
    if(st==en) {
        // lx와 rx 사이에 있을경우 true
        if(lx<=gun[st] && gun[st] <= rx) return 1;
        return 0;
    }
    
    int mid = (st+en)/2;
    if(gun[mid] <lx) return binsearch(mid+1, en, lx, rx);
    else return binsearch(st, mid, lx, rx);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> M >> N >> L;
    for(int i=0; i<M; i++) cin >> gun[i];
    for(int i=0; i<N; i++) {
        int x,y; cin >> x >> y;
        animal[i] = make_pair(y,x);
    }
    
    // 사대 정렬
    sort(gun, gun+M);
    
    int cnt=0;
    // 모든 동물에 대해 잡을 수 있는 사대 있는지 확인
    for(int i=0; i<N; i++) {
        int ey = animal[i].first;
        int ex = animal[i].second;
        
        int dy = L - ey;
        if(dy < 0) continue;
        
        // x좌표 내에 사대 있으면 카운트 증가
        if(binsearch(0,M-1,ex-dy, ex+dy)) cnt++;
    }
    cout << cnt << '\n';
    
    return 0;
}
 

문제유형

• 이진탐색 - 모든케이스에서 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1920
• https://www.acmicpc.net/problem/8983
• https://www.acmicpc.net/problem/3020
• https://www.acmicpc.net/problem/2143
• https://programmers.co.kr/learn/courses/30/lessons/43238