[백준 8983번] 사냥꾼 (java)

8983번: 사냥꾼

 

이 문제는 이분탐색을 이용하여 해결할 수 있다.

 

사대의 위치를 arr 배열에 오름차순으로 정렬한다.

정렬 전 : 6 1 4 9

정렬 후 : 1 4 6 9

 

특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다.

이분탐색을 진행하는 방법은 다음과 같다.

 

arr[middle] == x

이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가 가장 짧으므로 middle 위치를 반환한다.

 

arr[middle] < x

이분탐색 범위(left ~ right)에서  arr[middle]가 동물의 x좌표보다 작다면,

left = middle + 1로 변경한다. 사대가 동물의 왼쪽에 있을 때는 오른쪽에 있는 사대일수록 동물간의 거리가 좁아지기 때문이다.

 

 

arr[middle] > x

이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표보다 크다면,

right = middle -1로 변경한다. 사대가 동물의 오른쪽에 있을 때는 왼쪽에 있는 사대일수록 동물간의 거리가 좁아지기 때문이다.

 

 

이렇게 이분탐색으로 특정 동물과 가장 가까운 위치에 있는 사대를 구한 후,

해당 사대와 동물간의 거리가 L보다 작거나 같다면 그 동물은 사냥을 당하기 때문에 count를 증가시킨다.

 

동물의 수인 N만큼 반복했을 때 최종 count가 사냥을 할 수 있는 동물의 수가 된다.

 

 

소스코드 :