[백준] 8983 : 사냥꾼

문제

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

첫번째 풀이

23점 부분점수 받음

import sys
m, n, l = map(int, sys.stdin.readline().split())
s = list(map(int, sys.stdin.readline().split()))
d = [[0 for i in range(2)] for j in range(n)]

for i in range(n):
    d[i] = list(map(int, sys.stdin.readline().split()))
      
d = sorted(d)
dict = {} # x축 좌표에서 가질 수 있는 최대 사정거리 : {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 7: 0, 8: 0, 9: 0}
for i in range(n):
    dict[d[i][0]] = 0 

c = [] # 최대 점 : [[6, 4], [1, 4], [4, 4], [9, 4]]
for i in s:
    c.append([i, l])

def rec(x, y): # 변화된 dict : {1: 4, 2: 3, 3: 3, 4: 4, 5: 3, 7: 3, 8: 3, 9: 4}
    if y <= 0:
        return
    
    if x in dict.keys():
        tmp = max(dict.get(x), y) # max 값인 것을 넣어줌
        dict[x] = tmp
    
    rec(x-1, y-1)
    rec(x+1, y-1)    
    
for i in range(len(c)):
    rec(c[i][0], c[i][1]) 

count = 0
for i in range(len(d)):
    if dict.get(d[i][0]) >= d[i][1]:
        count += 1
    
print(count)

막힌 부분

사대를 기준으로 잡지않고, 동물을 기준으로 잡을 수 있는 사대가 범위 내에 존재하는지 확인하는 것까진 힌트를 봐서 알겠다.

그런데,
이분탐색을 어디에서 진행해줘야 하는지를 잘 모르겠다.

만약 (7, 2)에 동물이 있다고 하면,
그 동물을 잡을 수 있는 사대의 범위는

s = x + y - L
e = x - y + L

이어서

5와 9 사이에 사대가 존재하면 동물이 잡힐 수 있는 것이다.

5와 9 사이에 target (사대)가 존재하는지 봐주기 위해 이분탐색을 진행하는 것처럼 보이는데, 이건 그냥 if target >= start and target <= end 이면 count를 1개 더 올려주면 되는 게 아닌가...? 라는 생각을 하게 된다.

구조

보통 이진탐색하면
배경과 찾으려고 하는 값(타겟 // 이진탐색에 가지고 들어가는 값)이 있는 걸 생각한다.
배경은 찾으려고 하는 값이 있는 배열 등을 생각하면 된다 (검색 대상이라는 말을 쓰지만, 타겟과 의미가 헷갈려서 그렇게 쓰겠다.

예를 들어, 여기에선 찾으려고 하는 값이 12라면

12가 타겟,
배열이 배경(찾으려고 하는 값이 있는 배열)이라고 보면 된다.

이 문제에선
배경이 사대이고 찾으려고 하는 값이 각 동물 당 사냥될 수 있는 사대의 범위이다.

어려운데, 풀어서 말하면
사대라는 배열에서, 타겟, 즉 일치하는 특정 수가 동물별 사대범위인 것이다.

이때 타겟이 범위이므로 보통 이진탐색처럼

   while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다 // 타겟이 있으면 인덱스 리턴
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

이렇게 data[mid] == target으로 진행되는 것이 아니라,
각 동물별로 사대가 있어야 하는 범위인
s (= x+y-l) <= x <= e (= x-y+l)를 구하고 이 범위 안에 사대가 있으면 count += 1을 해주는 구조를 가지고 있다.

    while start <= end:
        mid = (start + end) // 2
        
        if sade[mid] >= s and sade[mid] <= e:
            count += 1 # 해당 동물에 대한 사대 찾았으므로 count += 1
            break
        elif sade[mid] < s: # 사대가 있는 곳이 동물에 대한 사정 거리보다 작음 => 사대가 있는 곳을 크게 해야
            start = mid + 1
        elif sade[mid] > e: # 사대가 있는 곳이 동물에 대한 사정 거리보다 큼 => 사대가 있는 곳을 작게 해야
            end = mid - 1

22.04.12 다시 풀어보기

일단 기본적인 아이디어인, 동물의 위치를 기준으로 사정거리가 주어졌으므로
동물별로 위치에서 사대가 있어야만 하는 범위 안에 사대가 들어가 있는지를 count해주는 생각까진 잘 했다.

그러나, 이분탐색을 어디서 어떻게 써야 하는지를 놓쳤다.

검색 대상은 사대가 들어있는 리스트이다.
해당 사대 리스트에서 target으로 동물이 사냥되려면 사대가 위치해야 하는 범위에 사대가 있는지 확인해주는 것이 필요했다.

즉, 정리해보면
검색대상 : 오름차순으로 정렬된 사대
검색타겟 : 동물별 사대가 위치해야 하는 범위
start : 사대에서 가장 작은 값인 첫번째 인덱스 0
end : 사대에서 가장 큰 값인 마지막 수의 인덱스 M - 1

import sys
M, N, L = map(int, sys.stdin.readline().split())
sade = sorted(list(map(int, sys.stdin.readline().split())))
ani = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def bsearch():
    # 검색 대상 : 사대
    # 검색 타겟 : ani가 사냥되려면 사대가 위치해야 하는 범위 
    # 이진탐색 진행 방향 : 각 ani별로 사냥되려면 사대가 위치해야 하는 범위에 사대가 있는지 이진탐색으로 찾는다.
    
    # 사대의 인덱스
    cnt = 0
    for x, y in ani:
        start = 0 # 이걸 밖에다 둬서 갱신이 계속 안 됐어서 틀렸다! (실수한 부분)
        end = M - 1
        a = x + y -L
        b = x - y + L
        while start <= end:
            mid = (start + end) // 2 # 현재 사대의 인덱스
            # print('사대 위치', a, b, sade[mid])
            if sade[mid] >= a and sade[mid] <= b:
                cnt += 1
                break
            elif sade[mid] < a: # 목표했던 사대의 위치보다 작은 곳에 사대가 있으면 사대가 더 큰 곳에 위치해야 함
                start = mid + 1
            elif sade[mid] > b: # 목표했던 사대의 위치보다 큰 곳에 사대가 있으면 사대가 더 작은 곳에 위치해야 함
                end = mid - 1
    
    return cnt
        

print(bsearch())

정답 풀이

import sys

m, n, l = map(int, sys.stdin.readline().split())
sade = list(map(int, sys.stdin.readline().split())) # 사대의 x축 좌표 리스트
animal = list(map(int, sys.stdin.readline().split()) for _ in range(n)) # 2차원 배열 [x축, y축]

sade.sort()

# 동물 기준으로 사대 찾기
count = 0
for x, y in animal: # 동물의 x축, y축 좌표
    if y > l: # 동물이 사정거리보다 높은 곳에 있으면 사냥 X (반복문 조기 종료 조건)
        continue 
    s = x+y-l # x, y 좌표별로 s, e를 계산 (동물별 사냥되려면 사대가 있어야 하는 범위)
    e = x-y+l
    
    # 검색대상 : 사대
    start = 0
    end = len(sade)-1
    
    while start <= end:
        mid = (start + end) // 2
        
        if sade[mid] >= s and sade[mid] <= e:
            count += 1 # 해당 동물에 대한 사대 찾았으므로 count += 1
            break
        elif sade[mid] < s: # 사대가 있는 곳이 동물에 대한 사정 거리보다 작음 => 사대가 있는 곳을 크게 해야
            start = mid + 1
        elif sade[mid] > e: # 사대가 있는 곳이 동물에 대한 사정 거리보다 큼 => 사대가 있는 곳을 작게 해야
            end = mid - 1

print(count)