8983. 사냥꾼

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

8983번: 사냥꾼

 

티어는 골드4, 완성하는데 15~20분 정도 걸렸다.

이진탐색(Binary Search)를 활용하여 해결하였다.

 

코드의 가독성을 높이기 위해서 main 함수의 코드를 줄이고, 함수를 활용하여 코드를 나누어보았다.

앞으로도 이렇게 코딩하는 습관을 가지도록 해야겠다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;

int n, m, l, ans;
int shot[100005];

struct xy{
    int x;
    int y;
} animals[100005];

void input(){
    scanf("%d %d %d", &m, &n, &l);
    for(int i=0 ; i<m ; i++) scanf("%d", &shot[i]);
    for(int i=0 ; i<n ; i++) scanf("%d %d", &animals[i].x, &animals[i].y);
}

int minDistance(int i, int left, int right){
    if(abs(left-right) <= 1){
        int leftDistance = abs(shot[left]-animals[i].x);
        int rightDistance = abs(shot[right]-animals[i].x);
        if(leftDistance < rightDistance) return leftDistance;
        else return rightDistance;
    }

    int mid = (left + right)/2;
    if(shot[mid] > animals[i].x) return minDistance(i, left, mid);
    else return minDistance(i, mid, right);
}

int main()
{
    input();

    sort(shot, shot+m);

    for(int i=0 ; i<n ; i++){
        if(minDistance(i, 0, m-1) + animals[i].y <= l) ans++;
    }

    printf("%d", ans);
}