백준 8983 사냥꾼 풀이

문제

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

8983번: 사냥꾼

 

풀이

우선 모든 사대에 대해 잡을 수 있는 것을 다 판단하고, 그중 중복되는 것을 지우고하는 것은 시간복잡도 상 맞지 않을 것이다.O(MN)

사대의 범위를 보자. 사대의 x좌표가 p라고 한다면

y <= x - p + L (x <= p)

y <= -x + p + L (x > p)

로 정리 가능하다.(y > 0이라는 조건이 필요할 것 같지만 오히려 동물의 y좌표가 양수이므로 상관 안해도 된다.)

사대의 위치들을 정렬한 배열을 P라고 하자.

P[i] = p1, P[i+1] = p2라고 하면 (p1 < p2) 

-x + p1 + L = x - p2 + L이므로 x = (p1 + p2)/2에서 교점이 생긴다. 이를 X라하자.

i번째 사대의 범위에서, x > X라면 i+1번째 사대의 y값이 더 클 것이므로 x > X에선 i번째 사대범위를 굳이 신경 안써도 된다. 동일한 x값에서 y값이 더 클수록 더 많은 동물을 포함가능하다.

역시나 i+1번째 사대의 범위에서 x < X라면 i번째 사대의 y값이 더 크다.

포인트는 특정 x값에서 y값이 제일 큰 사대만 챙긴다는 것이다.

 

여기서 모든 x값에 대해서 판단하기엔 무리가 있으므로 좌표압축을 해준다. 우린 동물의 좌표로서 주어진 x값만 판단해주면 된다.

 

우리가 필요한건

1. 압축한 x값에서 주어진 사대의 범위안에 들어올 수 있는 가장 큰 y값을 담는 map(dict)인 maxy

2. 사대의 좌표를 정렬한 P

이다.

이제  maxy의 값을 채워주면 된다.

구현방법은 여러가지 있으나 이 방법을 이용하였다.

//로직을 보여주기 위한 의사 코드
maxy = {x1:0,x2:0,x3:0,....}
xq = queue([x1,x2,x3,...]) // 압축한 동물좌표 x값을 담는 큐
for (int i = 0;i<P.length;i++){
   cur = P[i]
   if (i == P.length - 1)
      nxt = 10 ** 12 #매우 큰 값
   else:
      nxt = P[i+1]
   // 다음 사대와의 교점을 구하기위한 nxt, 만약 마지막 사대라면 큰 값을 줘서 정답에 영향가지않게함
   while(!xq.empty() && xq[0] <= (cur + nxt)/2){
       x = xq.popleft()
       if (x == cur) maxy[x] = L
       else if (x < cur){
          y = x - cur + L
          maxy[x] = y
       }
       else {
          y = -x + cur + L
          maxy[x] = y
       }
   }
}

이제 동물을의 좌표 x,y를 하나씩 보면서

y <= maxy[x]라면 정답에 추가해주면 된다.