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

문제

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

3020번: 개똥벌레

 

풀이

석순과 종유석을 별도의 리스트에 담아 정렬한 후, 이진 탐색을 진행하면 얼마나 많은 장애물을 파괴해야 하는지 구할 수 있다. 이때, bisect 모듈을 사용하면 좀 더 간결하게 코드를 짤 수 있다. 해당 함수들은 리스트에서 특정 값이 삽입될 인덱스를 반환한다.

bisect_left(arr, value)
bisect_right(arr, value)

bisect — 배열 이진 분할 알고리즘 — Python 3.9.6 문서

 

 

리스트 원소의 수(n//2)에서 반환된 인덱스를 빼주면 파괴해야 할 장애물을 구할 수 있다. 이를 코드로 표현하면 다음과 같다. 여기서 종유석(tops)의 경우엔 값을 변환해줘야 한다. 나는 간단하게 상하를 뒤집는 방식으로 생각했는데, 직접 숫자를 넣어보면 금방 이해될 것이다.

top_idx, bot_idx = bisect_left(tops, (t+1)-h), bisect_left(bottoms, h)
obs_cnt = n - (top_idx+bot_idx)    # (n//2 - top_idx) + (n//2 - bot_idx)

 

이와 같이 매 높이(h)마다 이분 탐색을 진행하면서 최솟값을 갱신해주면 답을 구할 수 있다.

 

 

코드

import sys
from bisect import bisect_left

def search():
    min_value = float('inf')
    cnt = 1
    for h in range(1, t+1):
        top_idx, bot_idx = bisect_left(tops, (t+1)-h), bisect_left(bottoms, h)
        obs_cnt = n - (top_idx+bot_idx)
        if obs_cnt < min_value:
            min_value = obs_cnt
            cnt = 1
        elif obs_cnt == min_value:
            cnt += 1
    return min_value, cnt


n, t = map(int, sys.stdin.readline().split())
tops, bottoms = [], []

for i in range(n):
    height = int(sys.stdin.readline().strip())
    if i % 2 == 0:
        bottoms.append(height)
    else:
        tops.append(height)

tops.sort()
bottoms.sort()

print(*search())