BOJ 8893(사냥꾼)풀이

solved.ac 티어 : 골 4

 

 

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

8983번: 사냥꾼

오랜만에 시험 끝나고 돌아왔다 당연히 시험은 망했고 오랜만에 와서 풀이를 쓸려고 한다

이 문제는 KOI 2013 중등, 고등 1번 문제이다

이 문제는 자명 풀이가 이분 탐색(binary search)이라는데 그것보다 스위핑처럼 하는 방법이 먼저 떠올라 그걸로 풀었다

 

방법은 이분 탐색만큼 간단한데 동물들의 점의 위치를 x, y으로 정렬하고 사냥꾼의 위치도 정렬한 다음

동물들의 수만큼 가장 왼쪽 x부터 탐색을 해주면 된다. 

i번째 사냥꾼과 j번째 동물의 거리가 L 이하면 바로 개수에+1해 주면 되고 아닐 경우 2가지 조건이 생기는데 바로 j번째 동물의 x 보다 i번째 사냥꾼의 x 가 더 큰 경우와 더 작은 경우로 나눠진다.

일단 사냥꾼의 x가 더 큰 경우는 j에만 +1을 해주면 된다.

동물과 사냥꾼을 x좌표로 정렬을 했기 때문에 다음 동물, 사냥꾼의 x는 같거나 더 크기 때문에 다음 동물이 현재 사냥꾼보다 더 가까울 수도 있기 때문에 i는 그대로 하고 j는 탐색이 끝났으니 +1해 주면 된다.

 

사냥꾼의 x보다 동물의 x가 더 큰 경우에는 따로 처리해줘야 되는 게 생긴다.

x가 더 크고 다음 동물들의 x값은 더 크기 때문에 i+1을 해줘야 된다고 생각할 수 있지만 잘 생각해보면 그렇지 않다.

위 그림과 같이 A1를 사냥꾼이라고 두고 파란색 선까지 범위를 사냥꾼의 범위라고 하자

이때 x가 더 가까운 A는 거리가 4 이상이지만 x의 거리가 더 먼 B는 거리가 3이 된다. 이처럼 x가 더 가까운 점이 i번째 사냥꾼의 범위 안에 안 들어갔다고 해도 다음 값이 안 들어가지는 않는다.

이걸 해결하는 방법도 의외로 간단한데 i번째 사냥꾼과 i+1 번째 사냥꾼과의 거리에서 중간까지 안에 들어가는 동물들을 추가로 처리해주면 된다.

 

A1과 D가 사냥꾼의 위치고 L(사냥꾼의 범위)가 2라고 했을 때 A1에서 y는 같고 x가 오른쪽으로 2칸 간 위치는 A1와 D 사냥꾼에게 모두 선택되는 위치이다. 여기서 +1을 더하면 A1에는 포함되지 않지만 D에는 포함되지 않는다. 

즉 i번째 와 i+1번째 사냥꾼의 정가운데까지는 A1안에 들어가기 때문에 처리하고 그다음부터는 다음 i 사냥꾼의 범위가 더 가깝기 때문에 그쪽에서 처리해주면 된다. 어차피 둘 중 하나라도 포함되면 되는 거니 더 가까운 쪽에서 처리해주면 된다.

 

그러니 두 위치의 중간 거리까지 반복으로 탐색을 해주면서 거리 안에 포함되는지 판별을 해주고 j+=1을 해주면 된다.

이미 i번째 사냥꾼에서 탐색이 되었고 중간거리까지에서는 i+1번째 사냥꾼보다 i 번째 사냥꾼이 더 가깝기 때문에 다음 사냥꾼에서 처리해줄 필요가 없다.

이렇게 돌면서 모든 사냥꾼이 탐색되거나 모든 동물들이 탐색이 될 때 끝내주면 된다.

import sys,math
inf=math.inf
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
a,b,c=map(int,input().split())
l=list(map(int,input().split()))+[inf]
t=[list(map(int,input().split()))for i in range(b)]+[[inf,inf]]
l.sort()
t.sort()
cnt=0
r=0
zx=[]
i=0
while i<b:
    if t[i][1]>c:i+=1;continue
    gh=0
    if abs(t[i][0]-l[r])+t[i][1]<=c:cnt+=1
    while t[i][0]>l[r]and abs(t[i][0]-l[r])+t[i][1]>c and r<a:
        gh=1
        while t[i][0]<=l[r]+((l[r+1]-l[r]+1)//2-1)and i<b:
            if abs(t[i][0]-l[r])+t[i][1]<=c:cnt+=1
            i+=1
        if i==b:print(cnt);sys.exit()
        r+=1
    if gh==0:
        i+=1
    if r==a:break
print(cnt)

시복은 O(nlogn)인 거 같다.

 

이분 탐색으로 하는 방법은

https://nnnlog.tistory.com/3

백준 8983번, 한국정보올림피아드(KOI) 2013 고등부 1번, 사냥꾼 풀이

이분 블로그를 참고해주세요