[백준] 8983 사냥꾼

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

각 동물의 위치를 기준으로 하여 사정거리를 계산하여 X축과 만나는 가장 먼 좌표의 값을 구하였습니다.

X축의 하나의 좌표와 접할수도 있고, 두개의 좌표가 나올 수 있습니다.

정렬된 사대를 이분 탐색을 이용하여 두 좌표의 사이에 존재하는 사대가 있는지 여부를 탐색하였습니다.

2) 알고리즘

• 이분탐색
• 재귀

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(left, right, targets):                     # 반복문 이용한 이분 탐색
    while left <= right:
        mid = (left+right) // 2                         # 탐색할 사대의 인덱스

        if targets[0] <= sites[mid] <= targets[1]:      # 현재 사대가 사정거리 범위 안에 포함된다면
            return True                                 # true 반환
        elif sites[mid] <= targets[0]:                  # 사정거리 범위 밖이라면
            left = mid + 1                              # 다음 탐색을 위한 인덱스 조정
        elif sites[mid] >= targets[1]:
            right = mid - 1
    return False                                        # 모든 사대가 사냥 불가능하면 False 반환

def solution2(left, right, targets):                    # 재귀를 이용한 이분 탐색
    global answer

    if left > right:                                    # 왼쪽 인덱스가 오른쪽 인덱스 보다 크면 종료
        return

    mid = (left+right) // 2                             # 탐색할 인덱스

    if targets[0] <= sites[mid] <= targets[1]:
        answer += 1        
        return
    elif sites[mid] <= targets[0]:                      # 인덱스 조정 후 재귀 호출
        solution2(mid+1, right, targets)
    elif sites[mid] >= targets[1]:
        solution2(left, mid-1, targets)

M, N, L = map(int, sys.stdin.readline().split())                                # 사대 수, 동물 수, 사정거리
sites = sorted(list(map(int, sys.stdin.readline().split())))                    # 사대 위치들 (오름차순 정렬)
animals = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]     # 동물들 위치 좌표
answer = 0

for x, y in animals:                    # 동물 위치 좌표 하나씩 탐색
    x1 = x - (L- y)                     # 사정거리의 최대 거리의 사대 위치
    x2 = x + (L -y)

    if solution(0, M-1, (x1, x2)):      # 사정거리 내에 있는 사대 탐색
        answer += 1                     # 있으면 잡을 수 있는 동물 추가
    
    # solution2(0, M-1, (x1, x2))       # 재귀 이용한 이분 탐색

print(answer)

---

🔗 문제 링크

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

8983번: 사냥꾼

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다