BOJ 8983 : 사냥꾼

알고리즘 문제 전체 링크

 

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

 

참고 

- 머지 소트 Merge Sort

 

 

어떤 동물이 사대에서 잡을 수 있는 동물이라면, 이 동물을 기준으로 가장 가까운 사대만 확인하면 된다.

즉, 동물을 기준으로 왼쪽과 오른쪽 사대에 대해서만 거리를 계산해 L과 비교하면 된다.

왼쪽과 오른쪽 사대가 동물을 사냥할 수 없다면, 다른 사대는 더 멀리 있으므로 검사할 필요가 없다.

 

사대의 좌표(= x)를 작은 순으로 정렬하고, 동물도 x 좌표를 기준으로 정렬한다.

모두 정렬했으니, 사대의 좌표가 animal보다 가장 가깝게 작은 곳을 찾을 수 있다.

while (index != M - 1 && place[index + 1] <= animal[i].x) index++;

 

동물을 기준으로 왼쪽 place[index]과 오른쪽 place[index + 1] 사대를 구했으니

계산을 해서 L보다 작거나 같으면 해당 동물을 센다.

if (calculate(place[index], animal[i].x, animal[i].y) <= L
	|| calculate(place[index + 1], animal[i].x, animal[i].y) <= L)
{
	ans++;
	continue;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (100100)

int M, N, L;

typedef struct st
{
	int x;
	int y;
}ANIMAL;

ANIMAL animal[MAX];
int place[MAX];

int b[MAX];
void merge(int* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end; i++)
		a[i] = b[i - start];
}

void sort(int* a, int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;
	sort(a, start, mid);
	sort(a, mid + 1, end);
	merge(a, start, end);
}

ANIMAL b1[MAX];
void merge(ANIMAL* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (a[i].x <= a[j].x) b1[k++] = a[i++];
		else b1[k++] = a[j++];
	}

	while (i <= mid) b1[k++] = a[i++];
	while (j <= end) b1[k++] = a[j++];

	for (i = start; i <= end; i++)
		a[i] = b1[i - start];
}

void sort(ANIMAL* a, int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;
	sort(a, start, mid);
	sort(a, mid + 1, end);
	merge(a, start, end);
}

int abs(int x)
{
	return (x > 0) ? x : -x;
}

int calculate(int place, int x, int y)
{
	return abs(place - x) + y;
}

int main()
{
	scanf("%d %d %d\n", &M, &N, &L);

	for (int i = 0; i < M; i++) scanf("%d", &place[i]);
	for (int i = 0; i < N; i++) scanf("%d %d", &animal[i].x, &animal[i].y);

	sort(place, 0, M - 1);
	sort(animal, 0, N - 1);

	int ans, index;

	ans = index = 0;
	for (int i = 0; i < N; i++)
	{
		while (index != M - 1 && place[index + 1] <= animal[i].x) index++;

		if (calculate(place[index], animal[i].x, animal[i].y) <= L
			|| calculate(place[index + 1], animal[i].x, animal[i].y) <= L)
		{
			ans++;
			continue;
		}
	}

	printf("%d\n", ans);

	return 0;
}