[JAVA/백준/8983] 사냥꾼

문제 요약

1. x 축에 사대가 있고 (a,b)에 동물이 존재함 사대로부터 거리가 L 이하인 동물만 잡을 수 있다고 가정했을 때 잡을 수 있는 동물의 수 찾기
2. 사대의 위치 x와 동물의 위치 (a, b) 간의 거리는 |x-a| + b

 

풀이

1. 동물들의 위치를 기준으로 반복문으로 돌림
2. 해당 동물을 잡을 수 있는 사대는 y좌표 - (L-x좌표)부터 y좌표 + (L-x좌표)
3. 사대의 위치를 정렬하여 min 값보다 크거나 같은 사대의 idx를 구함 (lowerbound)
4. 해당 idx의 사대 위치가 min 이상 max 이하일 경우 정답에서 1 증가

 

---

 

• 또 또 또 블로그 글을 보고 힌트를 얻은,,, ㅠㅠ
• 어차피 min의 값보다 같거나 큰 gun의 위치를 찾는 건데 if (gun[idx] <= max)로만 하면 틀리고 if (gun[idx] >= min && gun[idx] <= max) 해야 통과한다 이유가 뭐지...

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		int[] gun = new int[M];
		int[][] animal = new int[N][2];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			gun[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 2; j++) {
				animal[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Arrays.sort(gun);

		int answer = 0;
		for (int i = 0; i < N; i++) {
			if (L < animal[i][1])
				continue;

			int min = animal[i][0] - (L - animal[i][1]);
			long max = animal[i][0] + (L - animal[i][1]);
			int idx = lowerBound(gun, min > 0 ? min : 0);
			if (gun[idx] >= min && gun[idx] <= max)
				answer++;

		}

		System.out.println(answer);
	}

	private static int lowerBound(int[] gun, int target) {
		int l = 0;
		int r = gun.length - 1;

		while (l < r) {
			int mid = (l + r) / 2;
			if (gun[mid] < target)
				l = mid + 1;
			else
				r = mid;
		}
		return l;
	}

}