BOJ #3020 개똥벌레

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 3020. 개똥벌레

문제 풀이

주어진 범위에 대해 완전 탐색을 진행하나 해당 구간에서 부딪히는 장애물의 수를 구하는 과정을 이진 탐색을 사용해 $O(log\ n)$으로 줄임으로써 전체 시간복잡도를 $O(nlog\ n)$으로 만들어야 한다. 특히 이 문제는 binary search의 lower bound와 upper bound를 제대로 이해하면 바로 해결할 수 있었다.

• 항상 홀수 번은 석순, 짝수 번은 종유석이고 N은 언제나 짝수이므로 절반으로 나눠 두 배열에 별도로 입력받는다.
• 구간 h는 높이 h-1과 h 사이를 의미하므로 탐색은 1부터 H까지 진행한다.
• 따라서 1부터 H까지 순회한다고 할 때 석순은 h와 같거나 큰 개수이고(lower bound) 종유석은 H - [종유석 길이] < h (upper bound)를 만족하는 개수이다.
• bound를 다루는 두 개의 함수를 둘 필요 없이 석순의 경우 h번째 구간일 때 h-1에 대한 upper bound를 판별하면 종유석과 함께 같은 함수를 사용할 수 있다.
• 부딪히는 종유석, 석순의 개수는 각 장애물 개수 - upper bound 좌표가 되겠다.
• 모든 구간에 대해 순회하면서 최소값을 갱신하여 카운트한 뒤 결과를 리턴하면 된다.

python 코드

import sys
input = sys.stdin.readline

N, H = map(int, input().split())
suck, jong = [], []
for _ in range(N // 2):
    suck.append(int(input()))
    jong.append(int(input()))

def search(arr, val): # upper bound 판별
    l, r = 0, len(arr)
    while l < r:
        mid = l + (r - l) // 2
        if arr[mid] > val:
            r = mid
        elif arr[mid] <= val:
            l = mid + 1
    return len(arr) - l # val보다 작은 값 제외한 나머지

suck.sort()
jong.sort()
min_v, sol = N, 0
for h in range(1, H + 1):
    s = search(suck, h - 1) + search(jong, H - h)
    if s < min_v:
        min_v = s
        sol = 1
    elif s == min_v:
        sol += 1
print(min_v, sol)