[boj] 사냥꾼_8983JAVA

문제는 다음과 같다.

 

 

이 문제에서는 거리를 맨해튼거리로 계산하기 때문에 조금 더 난이도가 쉬운편!

각 플랫폼에서 맨해튼거리로 L 보다 같거나 작은 거리 내 동물들을 다 잡을 수 있다고 가정했을 때

잡을 수 있는 모든 동물의 수를 구하는 문제이다!

 

플랫폼의 수를 M,  동물의 수를 N, 거리를 L이라고 둔다.

 

플랫폼의 y좌표는 어짜피 0이므로, 플랫폼의 x좌표를 저장할 배열을 만들어준다. 값을 입력받고 오름차순 정렬해준다.

Long[] plate = new Long[M];
...
Arrays.sort(plate);

 

이렇게 된다면 plate[0] 에는 x축에 가장 가까운 사대가, plate[plate.length-1]에는 x축에서 가장 먼 사대가 되는 것이다.

 

동물의 x, y좌표를 입력받으면서

 

plate를 기준으로 start값과 end 값을 잡아준다.

가장 초기에는 start는 0, end는 plate.length-1로 둔다.

mid값은 (start + end)/2 이다.

 

이분탐색을 돌며 plate[mid]에서 해당 동물의 거리를 구하고, 그 값을 기준으로

1. L과 같거나 작으면 답을 추가한다.

2. L보다 크다면 ...

// 모든 사대는 y의 값이 0이다. 따라서 맨해튼 거리를 구할 때 mid값이 바뀌어도 x좌표끼리의 값만 바뀌지, y 값은 항상 일정하다.

    2-1. plate[mid] - x가 0보다 크다면, L과 같거나 작게 만드려면 plate[mid] 의 값이 줄어들어야된다. 따라서 mid값을 줄이기 위해 end값을 mid - 1 로 바꾼다.

    2-2. plate[mid] - x가 0보다 작다면, plate[mid] 값은 항상 양수기때문에 값이 커져야된다. 따라서 start값을 mid + 1로 바꾼다.

 

이렇게 이분탐색을 시행하면 문제가 풀린다!

이분탐색을 들어가기 전

동물의 y값이 L보다 이미 큰 상태라면 -> 모든 동물이 다 포함될 수 없으므로 이분탐색 하지말고 바로넘긴다!

이거까지 하면 실행속도가 더 줄어든다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int M = Integer.parseInt(st.nextToken()),
        N = Integer.parseInt(st.nextToken()),
        L = Integer.parseInt(st.nextToken());

        Long[] plate = new Long[M];
        st = new StringTokenizer(bf.readLine());
        for(int i=0;i<M;i++) {
            plate[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(plate);

        int ans = 0;
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(bf.readLine());
            Long x = Long.parseLong(st.nextToken()), y = Long.parseLong(st.nextToken());
            int start = 0, end = M-1;
            if(y > L) continue;
            while(start <= end) {
                int mid = (start+end)/2;
                Long target = plate[mid] - x;
                Long distance = Math.abs(target) + y;

                if(distance <= L) {
                    ans++;
                    break;
                } else if(target > 0) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }

        }

        System.out.println(ans);

    }
}