아이템의 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)에 탐색을 시도해본 결과 어림 없는 소리
kimsd1983 2년 전 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)는 안나옵니다.