[백준 2024/09/10] 8983번 사냥꾼

1. 문제

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

 

2. 접근 방법

 

동물의 위치가 (aj, bj) 라고 가정하고, 사정 거리가 L 이라고 가정한다.

이 때, x1에서 동물의 위치까지의 거리를 | xi - aj | + bj 라고 문제에서 가정한다.

따라서, aj에서 |xi- aj| 만큼의 거리 안에 사대가 있다면, 해당 동물을 사냥이 가능하다.

 

따라서, 문제의 첫 예시를 이용해서 구체화 해보도록 하겠다.

 

동물의 위치 좌표에서 L - y를 한 값을 y 좌표에 넣어준다. 그리고 이를 d 라고 명명한다.

만약, d가 음수라면, 사대에서 겨냥할 수 없을 정도로 y 값이 컸던 것이기 때문에 이는 count에서 제외 시킨다.

 

 

 

(3, 3)을 예시로 들면, L 이 4이므로 x 축에서 (4-3) 인 1 만큼 거리 안에 사대가 있어야 한다.

따라서, 2~4 위치에 사대가 있어야 한다.

 

처음엔 이를 2중 for문으로 작성하여 해결하였다.

하지만, 마지막 test case에서 실패하여 60점을 받았다. 60점을 받았던 코드는 아래와 같다.

def get_animal_location(n):
    animals = []

    for i in range(n):
        animal = list(map(int, input().split()))
        animals.append(animal)
    return animals


def find_animal_in_range(l, r, xs):
    for x in xs:
        if l <= x <= r:
            return 1

    return 0
def find_animals_in_range(l, n, animals, xs):
    for animal in animals:
        d = l - animal[1]
        animal[1] = d

    #print(animals)

    total = 0
    for x, d in animals:
        if d < 0:
            continue
        total += find_animal_in_range(x-d, x+d, xs)

    return total


if __name__ == "__main__":
    m, n, l = map(int, input().split())
    xs = list(map(int, input().split()))
    animals = get_animal_location(n)
    #print("animals:", animals)
    print(find_animals_in_range(l, n, animals, xs))

 

마지막 test case를 통과하기 위해선, 2중 for 문이 아닌, nlogn으로 코드를 작성해야겠다는 생각이 들었고

binary search를 적용시킬만한 부분을 찾기 시작했다.

 

사대를 입력 받은 리스트를 xs라고 선언했다.

xs를 sort한 후, find_animal_in_range(동물의 왼쪽 boundary, 동물의 오른쪽 boundary, xs, 사대의 개수) 를 입력 받는 함수를 작성하였다.

 

left = 0

right = 사대의 개수 - 1 로 선언하고, 

mid = ( left + right ) // 2 라고 하였다.

만약 xs[mid] 라는 사대가, 동물의 왼쪽 그리고 오른쪽 boundary 안에 속한다면, 해당 동물을 사냥이 가능한 것이므로, 1을 반환해 주었다.

그 외, 동물의 왼쪽 boundary보다 사대가 왼쪽에 있으면 left index 값을 mid + 1을 해주어, mid 값을 높일 수 있도록 하였다.

 

3. 코드

def get_animal_location(n):
    animals = []
    for i in range(n):
        animal = list(map(int, input().split()))
        animals.append(animal)
    return animals


def find_animal_in_range(l, r, xs, m):
    left = 0
    right = m-1

    while left <= right:
        mid = (left + right) //2
        if l <= xs[mid] <= r:
            return 1

        elif l > xs[mid]:
            left = mid + 1

        else:
            right = mid - 1

    return 0


def find_animals_in_range(l, n, animals, xs, m):
    for animal in animals:
        d = l - animal[1]
        animal[1] = d

    xs.sort() # binary search 이용 시, 꼭 정렬을 해야 한다.
    total = 0
    for x, d in animals:
        if d < 0:
            continue
        total += find_animal_in_range(x-d, x+d, xs, m)

    return total


if __name__ == "__main__":
    m, n, l = map(int, input().split())
    xs = list(map(int, input().split()))
    animals = get_animal_location(n)
    print(find_animals_in_range(l, n, animals, xs, m))