[알고리즘] 백준 - 개똥벌레

백준 - 개똥벌레

다른 사람 풀이 (이분 탐색)

N, H = map(int, input().split())

down, up = [], []
for i in range(N):
    if i % 2 == 0:
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = N
range_count = 0

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

for i in range(1, H+1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down)-1)
    top_count = len(up) - binary_search(up, H - i + 0.5, 0, len(up)-1)

    if down_count + top_count == min_count:
        range_count += 1
    elif down_count + top_count < min_count:
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

항상 이분탐색은 뭐를 이분 탐색의 대상으로 잡을지가 관건이다. 처음에는 나도 당연히 개똥벌레의 높이를 잡으려했으나, 그림만 보고 높이를 어떻게 하든 커질 수도 있고 작아질 수도 있어서 이분 탐색을 어떻게 쓸지 감이 안왔다.

포인트는 두 개다. 우선은 종유석과 석순을 구분해서 생각하는 것이다. 두 번째는 배열로 정렬해서 생각하는 것이다. 정렬을 하면, 특정 높이에서 벌레가 닿는다면 그 후는 모두 닿을 것이다.

그래서 그 높이의 개수와 최소 부딪치는 개수를 비교하면 된다.