https://www.acmicpc.net/problem/8983
8983번: 사냥꾼
입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌
www.acmicpc.net
이분탐색으로 접근했다.
풀이 방법
주어지는 사대의 위치를 오름차순으로 정렬한다.
이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.
이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.
해당 방법으로 접근한다면 O(100,000 * log100,000) 즉 O(500,000)에 탐색이 가능하다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [14923] 미로 탈출 (0) | 2024.04.21 |
|---|---|
| [13397] 구간 나누기 2 (0) | 2024.02.28 |
| [17471] 게리멘더링 (0) | 2024.02.06 |
| [1700] 멀티탭 스케줄링 (0) | 2024.01.30 |
| [23286] 허들 넘기 (0) | 2024.01.18 |