BOJ 3020: 개똥벌레 [Python 3]

귀여운 문제 제목과 다르게, 생각보다 어려웠던 문제였다.

이중탐색을 통해서 풀지 않으면, 계속 시간 초과가 났다.

코드를 통해서 설명하고자 한다.

import sys
input=sys.stdin.readline

def binary(h,arr):
    l,r= 0, len(arr)-1
    while l<=r:
        mid=(l+r)//2
        if arr[mid]<=h:
            l=mid+1
        else:
            r=mid-1
    return l

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

answer=[]
for i in range(h):
    answer.append(n-binary(i,down)-binary(h-i-1,up))
answer.sort()
print(answer[0],answer.count(answer[0]))

먼저, 석순과 종유석을 따로 리스트에 두고, sort한다.

이후에, 각 높이에 따라서 binary sort를 한다.

몇 개의 돌탑들을 만나는 지를 list에 넣어서, 최소 수와 개수를 구한다.

 

이런 곳에서도 binary sort를 쓴다니...!