8983. 사냥꾼

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	15860	5618	3841	34.569%

문제

KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, …, xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), …, (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다.

사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다.

예를 들어, 아래의 그림과 같은 사냥터를 생각해 보자. (사대는 작은 사각형으로, 동물의 위치는 작은 원으로 표시되어 있다.) 사정거리 L이 4라고 하면, 점선으로 표시된 영역은 왼쪽에서 세 번째 사대에서 사냥이 가능한 영역이다.

사대의 위치와 동물들의 위치가 주어졌을 때, 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌표 값이 빈칸을 사이에 두고 양의 정수로 주어진다. 이후 N개의 각 줄에는 각 동물의 사는 위치를 나타내는 좌표 값이 x-좌표 값, y-좌표 값의 순서로 빈칸을 사이에 두고 양의 정수로 주어진다. 사대의 위치가 겹치는 경우는 없으며, 동물들의 위치가 겹치는 경우도 없다. 모든 좌표 값은 1,000,000,000보다 작거나 같은 양의 정수이다.

출력

출력은 단 한 줄이며, 잡을 수 있는 동물의 수를 음수가 아닌 정수로 출력한다.

풀이

풀이 1 → sub task 2까지

input = __import__("sys").stdin.readline  
  
M, N, L = map(int, input().split())  
guns = list(map(int, input().split()))  
guns.sort()  
  
yList = [0] * (guns[-1] + L + 1)  
  
for g in guns:  
    for l in range(1, L):  
        yList[g] = L  
        if (g - 1 > 0) and (yList[g - l] < L - l):  
            yList[g - l] = L - l  
        else: break  
    for l in range(1, L):  
        if yList[g + l] < L - l:  
            yList[g + l] = L - l  
        else: break  
  
cnt = 0  
for _ in range(N):  
    x,y = map(int, input().split())  
    if len(yList) >= x and yList[x] >=  y:  
        cnt += 1  
print(cnt)

• 문제1: 메모리 초과 1번
  • yList가 최악의 메모리를 가지는 경우가 1000000000 + 1000000000 + 1임…
  • 이걸 파악하지 못하고 무지성으로 짬.
  • 앞으로 인풋값이 큰 경우나 시간초과, 메모리초과가 날때는 인풋 개수 보면서 하나하나 따져보기
• 문제2: 시간초과
  • 인풋값이 커지면 통과가 안되는건 어디선가 시간이 많이 투자되고 있는건데
  • 나는 원래 마지막 for문 동물 위치 받아서 잡을 수 있는 동물인지 확인하는 부분을 줄이려고 했음 그 위에 y_list 너무 깔끔하게 짰다고 생각해서..ㅋ
  • 그런데 사실 그 yList 만드는 부분이 문제였음. 생각해보면, 여기서 대부분의 연산을 다하고(뒤에서는 비교만 하면됨) 심지어 얘만 이중 for문인데.

풀이2 → sub task 3까지 통과

def findLR(n):          # n = 동물의 x좌표  
    S = 0               # guns 좌표값에 대한 인덱스  
    E = len(guns)-1  
    if n > guns[E]: return E, -1    # max(사대 좌표값 들) < 동물 좌표  
    elif n < guns[S]: return -1, S  # min(사대 좌표값 들) > 동물 좌표  
  
    while S < E:                    # upper bound 연산  
        mid = (S + E) // 2  
        if guns[mid] <= n:  
            S = mid + 1  
        else:  
            E = mid  
    if n == guns[S-1]: return S-1, S-1  # 이분탐색 결과 찾은 위치 -1의 값이 동물 좌표랑 동일하면,  
    else: return S - 1, E               # 아니면 범위 return  
M, N, L = map(int, input().split())  
guns = list(map(int, input().split()))  
guns.sort()  
cnt = 0  
for _ in range(N):  
    x, y = map(int, input().split())    # 동물 위치  
    s, e = findLR(x)                    # 동물 위치와 가장 가까운 사대 2개의 index    diff = 0  
    if s != e:  
        if e == -1:  
            diff = x - guns[s]  
        if s == -1:  
            diff = guns[e] - x  
        else:  
            diff = min(x - guns[s], guns[e] - x)  
  
    if y <= L-diff: cnt += 1  
print(cnt)

• yList로 다 세팅해놓는게 아니라, 동물 좌표 받으면 가까운 사대 위치를 이분 탐색으로 찾아서 연산하는 방식으로 변경

풀이3 → sub task 1로 돌아옴

def findUpper(n, arr):          # n = 동물의 x좌표  
    S = 0                       # guns 좌표값에 대한 인덱스  
    E = len(arr)  
    while S < E:                    # upper bound 연산  
        mid = (S + E) // 2  
        if arr[mid] <= n:  
            S = mid + 1  
        else:  
            E = mid  
    else: return E  
  
M, N, L = map(int, input().split())  
guns = list(map(int, input().split()))  
guns.sort()  
# 동물 받기  
animals = {}  
for _ in range(N):  
    x, y = map(int, input().split())  
    if x in animals:  
        animals[x] = animals[x].append(y)  
    else:  
        animals[x] = [y]  
  
cnt = 0  
for x in animals:  
    # 해당 x에서 쏠 수 있는 거리(gunY) 구하기  
    e = findUpper(x, guns)  # 오른쪽에서 가까운 사대의 위치  
    s = e-1             # 왼쪽에서 가까운 사대의 위치  
  
    diff = 0  
    if s < 0:           # 주어진 x가 가장 작은 사대 위치보다도 작은 값일때,  
        diff = guns[e] - x  
    elif e >= len(guns): # 주어진 x가 가장 큰 사대 위치보다도 큰 값일 때,  
        diff = x - guns[s]  
    else:  
        diff = min(x - guns[s], guns[e] - x)  
    gunY = L-diff  
  
    # 어느 동물까지 사정거리에 들어오는 지.  
    ys = animals[x]  
    ys.sort()  
  
    cnt += findUpper(gunY, ys)  
print(cnt)

• 동물 위치 다 받아서 x값 기준으로 dic을 만들고 이것 또한 정렬해서 이분탐을 돌림 = 어느 위치의 동까지 쏠 수 있는지 확인 용으로
• 저장했다 뺐다 하는 게 생각보다 품이 많이 들었음.

풀이4 → 성공

def findUpper(n, arr):          # n = 동물의 x좌표  
    S = 0                       # guns 좌표값에 대한 인덱스  
    E = len(arr)  
    while S < E:                    # upper bound 연산  
        mid = (S + E) // 2  
        if arr[mid] <= n:  
            S = mid + 1  
        else:  
            E = mid  
    else: return E  
  
M, N, L = map(int, input().split())  
guns = list(map(int, input().split()))  
guns.sort()  
cnt = 0  
dicY = {}  
  
for _ in range(N):  
    x, y = map(int, input().split())    # 동물 위치  
  
    # 해당 x에서 쏠 수 있는 거리(gunY) 구하기  
    if x in dicY:  
        gunY = dicY[x]  
    else:  
        e = findUpper(x, guns)  # 오른쪽에서 가까운 사대의 위치  
        s = e - 1  # 왼쪽에서 가까운 사대의 위치  
  
        diff = 0  
        if s < 0:  # 주어진 x가 가장 작은 사대 위치보다도 작은 값일때,  
            diff = guns[e] - x  
        elif e >= len(guns):  # 주어진 x가 가장 큰 사대 위치보다도 큰 값일 때,  
            diff = x - guns[s]  
        else:  
            diff = min(x - guns[s], guns[e] - x)  
        gunY = L - diff  
        dicY[x] = gunY  
  
    if y <= gunY: cnt += 1  
print(cnt)

• 일단 풀이 2로 돌아감
• 매번 이분탐색을 진행하는 건 품이 많이드니까
• 특정 x값에 대해서 탐색한 결과값을 dict에 저장해둠

Computer #PS