[BOJ/백준][Gold4] 8983 : 사냥꾼(C++)

www.acmicpc.net/problem/8983

8983번: 사냥꾼

 

 

[난이도] Gold4

[유형] 소팅,이분탐색

 

[풀이]

1. 사대와 동물을 x좌표 기준으로 오름차순으로 정렬
2. 모든 사대를 순회하면서 동물들을 잡을 수 있는지 체크한다. 동물과
   사대의 x좌표 차이의 절댓값이 다음 사대의 x좌표 절댓값보다 크면 다음
   사대로 넘어간다. (x좌표 절대값이 적은 사대가 가장 유리하기 때문)

 

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int M,N,L,p[100000],ans;
pair<int,int> ani[100000];
int main(){
    scanf("%d%d%d",&M,&N,&L);
    for(int i=0;i<M;i++) scanf("%d",&p[i]);
    for(int i=0;i<N;i++) scanf("%d%d",&ani[i].first,&ani[i].second);
    sort(p,p+M);
    sort(ani,ani+N);
    int j=0;
    for(int i=0;i<M;i++){
        for(;j<N;j++){
            if(i<M-1&& abs(ani[j].first-p[i]) > abs(ani[j].first-p[i+1])) break;
            if(abs(ani[j].first-p[i])+ani[j].second <= L) ans++;
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/8983.cpp