O(NM) 시간에 풀 수 있는 방법은 다음과 같다.동물의 좌표 (ai,bi)에 대해 사대의 좌표 (xj,0) 까지의 거리 |ai-xj| + bi 가 L 이하인 점을 j를 1부터 N까지 탐색하면서 찾는다.
O(N+M) 알고리즘은 다음과 같다.
동물의 x좌표 ai 근처에 있는 사대 xj 를 찾아서, xj <= ai <= xj+1 을 만족하도록 한다.
이 조건을 만족하면, j번째와 j+1번째 사대 두 경우만 확인하여 동물이 잡히는지 판단하면 된다. 먼저 사대와 동물의 위치를 각각 x좌표 순서로 정렬한다. 이후 동물을 x좌표가 작은 것 순서로 를 보면서, 사대의 이 만족하도록 j를 증가시킨다. i가 증가할수록 j도 항상 증가하기 때문에, i가 1부터 N까지 증가할 동안 j도 1부터 M까지만 탐색을 한다.