[#알고리즘/이진 탐색/[백준]3020번:개똥벌레(python)]

Question

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

Solution

1. N은 짝수이므로 절반으로 나누어 석순과 종유석을 두 배열에 나누어 입력받은 후 오름차순 정렬한다.
2. 구간 탐색은 1부터 H까지 진행한다.
3. 1부터 H까지 순회할 때, 석순은 구간 h와 같거나 큰 개수(lower bound)이고, 종유석은 H - (종유석 길이) < h 를 만족하는 개수(upper bound)이다.
4. upper bound를 찾는 함수를 정의한다. 종유석은 target을 H - h(구간)으로 주고, 석순은 h - 1로 주어 각각의 target을 기준으로 upper bound를 구한다. (석순의 경우, 위처럼 하면 lower bound를 찾는 함수를 따로 작성하지 않아도 된다.)
5. 각 부딪히는 석순과 종유석의 개수는 각 '장애물 개수 - upper bound 좌표'이다.
6. 모든 구간에 대해 순회하면서 최소값을 갱신한다.

Code

import sys
input = sys.stdin.readline

def search_upper(arr, target) :
    start, end = 0, len(arr)
    while (start < end) :
        mid = (start + (end - 1)) // 2
        if arr[mid] <= target :
            start = mid + 1
        else :
            end = mid 
    return len(arr) - end 
 
n, H = map(int, input().split())
seok, jong = [], []
for _ in range(n // 2):
    seok.append(int(input()))
    jong.append(int(input()))
    
seok.sort()
jong.sort()

result = 1e10   #기준값
range_cnt = 0


for h in range(1, H + 1):
    seok_cnt = search_upper(seok, h - 1)
    jong_cnt = search_upper(jong, H - h)
    cnt = seok_cnt + jong_cnt
  
    if cnt < result :
        result = cnt
        range_cnt = 1
    elif cnt == result :
        range_cnt += 1
 
  
print(result, range_cnt)

후기

upper bound와 lower bound의 개념을 몰라 처음 문제 접근부터 어려웠다. 후에 개념을 정리하고 막상 문제에 적용하자니 Solution에서 3번 이후로 문제 해결과정이 쉽지 않았다. 따라서 직접 그림을 그려가면서 문제를 해결하였다. 이 부분은 다른 문제를 풀어보면서 감각을 익혀야할 거 같다.

상한선(upper bound) : target보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘
하한선(lower bound) : target보다 같거나 큰값이 처음 나오는 위치를 리턴해주는 알고리즘