[백준] 3020번 개똥벌레 (Python 파이썬)

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

3020번: 개똥벌레

문제에 대한 자세한 설명은 위 링크에 기술 되어있다.

쉽게 풀어쓰자면 동굴의 길이(N)와 높이(H)를 입력받는다.

동굴은 석순과 종유석으로 구성되어 있는데, 석순은 아래에서 자라는 고드름 종유석은 천장에서 나는 고드름이라고 생각하면 된다. 

문제에서 동굴의 길이만큼 석순과 종유석의 길이를 입력받는데, 번갈아 가면서 입력받는다. ( 석순과 종유석은 각각 동굴의 길이 1만큼 차지한다)

예를 들어, 1 3 4 2 5 6 이라고 입력했으면 석순 1, 4, 5 / 종유석 3 2 6 이 되는 것이다.

이렇게 장애물이 설치된 동굴에 개똥벌레 한마리가 날라가는데 동굴의 높이가 6일 때, 개똥벌레가 날아가는 높이가 3이라고 한다면 아래에서부터 높이 2~3 (2.5라고 생각하면 쉽다) 구간을 날라간다. 

그래서 3보다 낮은 석순에는 모두 부딪히게 되고, 3보다 큰 종유석에는 모두 부딪히게 된다. ( 위에서 부터 4 만큼 내려온 종유석에는 아래에서 부터 2.5만큼 날아오른 개똥벌레가 부딪히기 때문)

 

이런 상황에서 문제에서 최종적으로 구하고자 하는 것은, 개똥벌레가 파괴해야 하는 장애물의 최소 개수와 이 최소값이 나오는 구간의 수를 구하는 것이다.

 

그렇다면 어떻게 접근해야 할까?

가장 먼저 떠오른 방법은 석순과 종유석의 배열을 따로 두고, 각각의 배열을 정렬 한 후에 처음 개똥벌레가 부딪히기 시작한 높이를 계산하는 방식이다. 왜냐하면 그 이후의 구간은 모두 부딪힌다는 이야기가 되기 때문에 첫 구간만을 구해 그 구간 전까지의 개수를 통해 답을 구할 수 있기 때문이다. 이러한 접근 방식을 누적 합(또는 구간합)이라고 하는데

현재 페이지에서는 다른 방식으로 풀어보려고 한다.

 

바로 이진탐색(Binary Search) 방식으로 풀려고 한다.

석순과 종유석의 배열이 각각 정렬되어 있기 때문에, 배열의 중간지점에서 개똥벌레가 부딪히는지 테스트를 진행한다.

보통의 이진탐색 과정과 마찬가지로 start값과 end값에 변화를 주며 mid값을 조정하여 개똥벌레가 최소한으로 부딪히는 구간을 찾으면 된다.

 

코드는 다음과 같다.

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 min_count == down_count + top_count:
        range_count += 1
    elif min_count > down_count + top_count: # 현재 범위가 새로운 최소 값이면
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

binary_search함수의 target은 개똥벌레의 높이가 되며 down일 때는 i - 0.5, up일때는 h - i + 0.5를 넣는다.

위에서 자라는 종유석의 경우에는 아래와는 반대로 생각해야 하기 때문이다.

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !