풀이
어떤 동물을 사냥할 수 있는지 판단해야한다.
그러기 위해선 어떤 동물에서 가장 가까운 어떤 사냥대를 찾아야 한다.
동물의 y좌표는 모든 사냥대에 대해 절대적인 반면,
x좌표는 사냥대에 대해 상대적이다.
그러므로 동물의 x좌표와 사냥대의 x좌표만 비교해서
O(1) 또는 O(log n)의 시간에 가장 가까운 사냥대를 찾을 수 있다.
O(1)은 적당히 반복문을 잘 굴리면 되고
O(log n)은 적당히 이분탐색 같은 걸 사용하면 된다. (안 해봤지만 아마 될 거다 ㅎ)
코드
#include <cstdio>
#include <algorithm>
using namespace std;
int m, n, l, ans, gun[100002];
pair<int, int> ani[100002];
int c(pair<int, int> p, int v) { return abs(p.first-v)+p.second; }
int main() {
scanf("%d %d %d", &m, &n, &l);
for (int i = 1; i <= m; i++) {
scanf("%d", &gun[i]);
}
for (int i = 1, x, y; i <= n; i++) {
scanf("%d %d", &ani[i].first, &ani[i].second);
}
sort(gun+1, gun+m+1); sort(ani+1, ani+n+1);
int p = 1;
for (int i = 1; i <= n; i++) {
while (p < m && gun[p+1] < ani[i].first) p++;
p -= p==m;
ans += min(c(ani[i], gun[p]), c(ani[i], gun[p+1])) <= l;
}
printf("%d\n", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이