kimsd1983   2년 전

아이템의 a,b 값에 이분탐색을 걸어서 딱 맞는 값이 없는 경우, 이분탐색이 끝난 지점을 기준으로 가까운 값으로 탐색을 시도하면 하아암정에 빠집니다.

만약 기력이 5, 목표 좌표가 5,5인데 주어진 아이템이 (-2,3), (-1,0), (-1,1), (6,2), (7,0), (7,7)라고 해봅시다.

(-2,3) 아이템을 사용한 상태에서 목표지점까지의 남은 거리인 (7,2)으로 탐색을 시도할 수 있겠죠?

여기서 이런 아이디어가 떠오를 수 있습니다.

- s<e 일 때 이분탐색을 시도하고 s == e가 되면 일치하는 아이템이 없는 것이므로 s-1을 반환한다.
- s가 N-1보다 작다면 s-1과 s에 대해 탐색을 시도해본다.

이분탐색의 결과, 일치하는 값이 없는 경우 마지막 s, e가 연속된 값이고 m이 목표하는 값보다 작게 됩니다.
그러면 s가 m+1로 바뀌는데 그 때 s가 목표 값을 넘어가버리니까 s-1을 반환하는 거죠. 꽤 괜찮은 것 같습니다.

그런데 이거 아이템의 y값에 대해서만 작동할 가능성이 있습니다. 이게 제가 올린 테케에서 어떻게 작동하냐면,

- (-2,3) 아이템을 사용하고 남은 기력 3
- 남은 거리 (7,2) 아이템이 있는지 이분탐색 돌림
- (7,2)를 넘지 않는 (7,0)이 반환됨
- (7,0)에 탐색을 시도해본 결과 기력 6이 필요함((-2,3)->(7,0)->y축으로 2칸 이동)
- (7,4)에 탐색을 시도해본 결과 어림 없는 소리
- (이후 가능성 없는 탐색)
- (6,2) 아이템을 사용하고 남은 기력 3
- 남은 거리 (-1,3) 아이템이 있는지 이분탐색 돌림
- (-1,3)을 넘지 않는 (-1,0)이 반환됨
- (-1,0)과 그 다음 아이템인 (-1,1)에 탐색을 시도해본 결과 어림 없는 소리

저도 제가 뭘 설명하고 싶은 건지 이제 모르겠습니다.

하지만 확실히 전해드리고 싶은 건 이거예용.

여기서 해야 하는 탐색은 단순 이분탐색이 아니라는 거죠... 왜냐면

(-2,3) 아이템을 들고 찾아야 하는 건 (6,2)니까요!!!

첫 아이템 쓰고 남은 좌표인 (7,2) 가지고 이분탐색을 돌리면 (6,x)는 안나옵니다.

ufshg   2년 전

어림 없는 소리 추

댓글을 작성하려면 로그인해야 합니다.