[ BOJ 백준 8983번 - 사냥꾼 ] 해설 및 코드

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

 

 

목적

사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 구하자.

접근법

1. n마리의 동물을 주어지는 순서대로 잡을 수 있는지 여부를 검사하자. 사대를 정렬한 뒤 이분 탐색으로 시간 복잡도를 낮추도록 하자.

 

2. 잡을 수 있는지는 a - (L-b) 이상 a + (L-b) 이하의 범위에 사대가 존재하는지 검사하면 된다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int h[(int)1e5];
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m,n,l;cin>>m>>n>>l;
    f(i,0,m)cin>>h[i];
    
    int *end=h+m;
    sort(h, end);
 
    int cnt=0;
    while(n--){
        int a,b;cin>>a>>b;
        int tmp=l-b;
        if(tmp<0)continue;
        if(upper_bound(h,end,a+tmp)-lower_bound(h,end,a-tmp)>0)
            ++cnt;
    }
    cout<<cnt;
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.