[3020] 개똥벌레 : 이분탐색
문제
https://www.acmicpc.net/problem/3020
설명
동굴의 길이는 N미터, 높이 H미터
석순 > 종유석 > 석순 > 정유석 순서대로 입력을 받는다.
개똥벌레는 구간을 날라다니면서, 석순과 정유석을 파괴한다.
개똥벌레가 파괴하는 장애물의 최소개수와, 그러한 구간의 개수를 구한다.
이분탐색
시간복잡도 = O(logN)
이분탐색은 !정렬!되어 있어야 한다.
upper_bound, lower_bound = 같은 값일 때 어떻게 처리할지를 추가한다.
upper_bound = x초과의 값이 처음으로 나타나는 위치
lower_bound = x이상의 값이 처음으로 나타나는 위치
문제풀이
구간은 1부터 H까지의 값을 가집니다.
구간이 1일때 파괴하는 석순과, 종유석의 개수를 구해봅시다.
석순의 개수 : 높이가 0보다 큰 석순을 모두 파괴합니다.
종유석의 개수 : 높이가 3보다 큰 종유석을 모두 파괴합니다.
구간이 2일때 파괴하는 석순과, 종유석의 개수를 구해봅시다.
석순의 개수 : 높이가 1보다 큰 석순을 모두 파괴합니다.
종유석의 개수 : 높이가 2보다 큰 종유석을 모두 파괴합니다.
특정 구간일 때 파괴할 수 있는 석순과 종유석의 개수를 구해보면서, 결국 구간이 h일때 파괴할 수 있는 석순/종유석의 개수를 일반화 할 수 있다.
구간이 h일때,
파괴하는 석순 개수 = 높이가 (h-1) 보다 큰 석순의 개수
파괴하는 종유석 개수 = 높이가 (H-h) 보다 큰 종유석의 개수
코드
import sys
N, H = map(int,input().split())
down_arr , up_arr = [], []
for i in range(N):
if i%2 == 0:
down_arr.append(int(input())
up_arr.append(int(input())
# 이분탐색은 정렬 되어 있어야 한다!
down_arr.sort()
up_arr.sort()
def upper_bound(arr, target)
left, right = 0, len(arr)-1
while left <= right :
mid = (left+right)//2
# 초과인 값 찾기
if target>=arr[mid]:
left = mid + 1 # 범위 좁히기
else:
right = mid - 1
# left와 right이 역전
# target 초과인 개수 구하기
return len(arr) - (right + 1)
# return len(arr) - left
cnt = 0
ans = sys.maxsize()
# 구간 탐색
for h in range(1, H+1):
석순 = upper_bound(down_arr, h-1)
종류석 = upper_bound(up_arr, H-h)
sum = 석순 + 종류석
if sum < ans :
cnt = 1
ans = sum
elif sum == ans:
cnt += 1
print(ans, cnt)