[백준 8983] 사냥꾼

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

8983번: 사냥꾼

#include <cstdio>
#include <iostream>
#include <algorithm>
int M, N, L;	// 사대 수, 동물 수, 사정거리
int base[100000 + 10];
struct _st
{
	int a;
	int b;
}animal[100000 + 10];

int cnt;


void input(void)
{
	scanf("%d %d %d", &M, &N, &L);
	for (int i = 0; i < M; i++) {
		scanf("%d", &base[i]);
	}
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &animal[i].a, &animal[i].b);
	}
}

int BS(int lb, int ub)
{
	int s = 0;
	int e = M - 1;
	int pivot = 0;

	while (s <= e) {
		pivot = (s + e) / 2;

		if (base[pivot] >= lb && base[pivot] <= ub) return 1;
		else if (base[pivot] < lb) s = pivot + 1;
		else if (base[pivot] > ub) e = pivot - 1;
	}
	return 0;
}

void shoot(void)
{
	std::sort(base, base + M);	// 사대 오름차순 정렬

	for (int i = 0; i < N; i ++ ) {
		int lb = -L + animal[i].b + animal[i].a;	// 부등식에 의해 하한선
		int ub = L - animal[i].b + animal[i].a;		// 부등식에 의해 상한선
		if (BS(lb, ub) == 1) cnt++;
	}
}

int main()
{
	input();
	shoot();
	printf("%d", cnt);
	return 0;
}

이 문제는 이분탐색이긴 한데 사실 부등식으로 해결했다. ㅋㅋㅋㅋ 4년 동안 공부한 수학 이렇게 써먹... ^^.. 뿌듯하다.. ^^;;

 

 

// shoot( ) 함수

사실 처음에는 사대를 기준으로 동물을 쏠 수 있는지 없는지를 판별하려고 했다. 근데 이렇게 접근하면 중복이 발생하기 때문에( 예컨대 1번 사대에서 쏜 동물을 4번 사대에서 쏠 수도 있음) "동물을 기준으로 사냥이 가능한지 아닌지" 판별해야 한다.

그전에 이분 탐색을 위해 #include <algorithm> 후 sort 라이브러리를 사용하여 사대를 오름차순으로 정렬해주었다. 

다음으로 N개의 동물들을 차례로 탐색하는데, 이때 해당 위치의 동물을 쏠 수 있는 사대의 좌표는 | x - a | + b <= L 이 부등식을 풀어주면 된다. 절댓값 벗기고 전개하면 -L + b + a <= x <= L - b + a 가 된다. 즉, 사대의 좌표의 하한선은 (-L + b + a) 이고 상한선은 (L - b + a)인 것이다. 

그리고 이분탐색으로 해당 범위 내에 사대가 존재하는지 판별해 주었다. 

 

 

// BS( ) 함수

base 배열을 탐색하면서 인자로 받은 하한선(lb) 보다 크고, 상한선(ub) 보다 작은 사대가 있는지 탐색한다. 

최초의 하나를 발견하면, 더 탐색할 것도 없이 해당 동물은 사냥할 수 있는 동물이기 때문에 return 1 후, cnt 값을 올려준다. 

만약 base[pivot] < lb 이면, 사대의 좌표가 하한선보다 작은 경우이기 때문에 s = pivot + 1로 시작점을 갱신하여 더 큰 위치에 있는 사대를 탐색한다. 

반면 base[pivot] > ub 이면, 사대의 좌표가 상한선보다 큰 경우이기 때문에 e = pivot - 1로 끝점을 갱신하여 더 작은 위치에 있는 사대를 탐색한다. 

만약, 사대의 위치가 저장된 base배열을 모두 탐색했는데도 lb와 ub 범위에 있는 원소가 나타나지 않으면 0을 리턴하고, 해당 동물은 잡을 수 없기 때문에 cnt값을 올려주지 않는다.