[Python] BOJ / 3020번 / 개똥벌레

3020번: 개똥벌레

---

📝 풀이

• 장애물(석순과 종유석)로 가득찬 동굴을 개똥벌레가 통과하고자 할 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 총 개수를 구하는 프로그램
• 이분 탐색 알고리즘을 통해 각각의 장애물(석순과 종유석)과 높이에 따라 파괴해야 하는 장애물의 첫 번째 인덱스를 구한 뒤 해당 인덱스를 통해 파괴해야 하는 장애물의 수를 구할 수 있음
  • 석순(down)을 파괴하는 경우는 개똥벌레가 날아가는 높이(target)를 (i - 0.5)로 설정하여 구할 수 있으며 종유석(up)을 파괴하는 경우는 높이를 (h - i + 0.5)로 설정하여 구할 수 있음
    
    • 첫 번째 구간은 높이 0과 1 사이인 0.5, 두 번째 구간은 높이 1과 2 사이인 1.5, 세 번째 구간은 높이 2와 3 사이인 2.5를 지나게 되므로
  • 위 과정에서 구한 파괴해야 하는 장애물의 수(total_cnt)가 현재까지 구한 최솟값(obs_cnt)과 같다면 구간의 개수(sec_cnt)를 증가시켜줌. 만약 파괴해야 하는 장애물의 수가 현재까지 구한 최솟값보다 작다면 최솟값을 갱신시켜주고 구간의 개수를 1로 초기화

---

💻 소스코드

import sys

input = sys.stdin.readline

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return left

n, h = map(int, input().split())

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

up.sort()
down.sort()

obs_cnt, sec_cnt = n, 0
for i in range(1, h + 1):
    up_cnt = len(up) - binary_search(up, h - i + 0.5)
    down_cnt = len(down) - binary_search(down, i - 0.5)
    total_cnt = up_cnt + down_cnt

    if obs_cnt == total_cnt:
        sec_cnt += 1
    elif obs_cnt > total_cnt:
        obs_cnt = total_cnt
        sec_cnt = 1

print(obs_cnt, sec_cnt)