[ BOJ 3020 ] 개똥벌레(Python)

문제

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

개똥벌레가 [석순-종유석-석순-..] 순으로 번갈아 등장하는 동굴을 지나갈 때,
최소한의 장애물에 부딪히도록 하는 높이를 찾는 문제다.

귀여운 제목에 이끌려 들어갔다가 큰 코 다친 문제 🐛

문제 풀이

처음에 높이를 이분 탐색해야 한다고 잘못 생각해서 오래 걸렸다.

높이는 순차적으로 탐색하고, 석순과 종유석 높이를 각각 이분 탐색해주면 된다. (🔗 참고)

1. 석순과 종유석을 입력 받고, 정렬해준다.

h_arr, l_arr = [], []

for i in range(n):
    t = int(input())
    if i % 2 == 0:
        l_arr.append(t)
    else:
        h_arr.append(t)

# 석순 l_arr / 종유석 h_arr
l_arr.sort()
h_arr.sort()

2. 높이가 h일때, 부딪히는 장애물의 개수를 체크하는 함수를 만든다.

def check(height, cave):
    # 개똥벌레 높이가 height일때
    l, r = 0, len(cave) - 1
    while l <= r:
        mid = (l + r) // 2
        if cave[mid] <= height:
            l = mid + 1
        else:
            r = mid - 1

    return len(cave) - (r + 1)

[개똥벌레가 높이 height로 날 때 장애물에 부딪히는 경우]

• 석순 석순의 높이가 height보다 클 때
• 종유석 (동굴 높이-종유석 높이)가 height보다 클 때

for i in range(1, h+1):
    l_cnt = check(i-1, l_arr)
    h_cnt = check(h-i, h_arr)
    cur_cnt = l_cnt + h_cnt

height보다 큰 요소의 개수는 부딪히는 장애물의 개수를 의미한다.

따라서 이분 탐색으로 범위를 줄여나가면서 height 가 들어갈 수 있는 적절한 위치를 찾아줄 것이다.

이분탐색이 끝나고 났을 때 r은 height가 삽입될 수 있는 위치를 반환한다.

즉 r+1 는 height보다 작은 값들의 갯수다.

우리는 height 보다 큰 값의 갯수를 구해야 하므로
부딪히는 장애물의 갯수는 (cave의 길이 - (r + 1)) 이다.

3. 가장 작은 장애물에 부딪히도록 하는 높이를 찾는다.

    if cur_cnt < answer:
        answer = cur_cnt
        answer_cnt = 1
    elif cur_cnt == answer:
        answer_cnt += 1
    else:
        pass

코드

import sys
input = sys.stdin.readline

def check(height, cave):
    l, r = 0, len(cave) - 1
    while l <= r:
        mid = (l + r) // 2
        if cave[mid] <= height:
            l = mid + 1
        else:
            r = mid - 1

    return len(cave) - (r + 1)


n, h = map(int, input().rsplit())
h_arr, l_arr = [], []

for i in range(n):
    t = int(input())
    if i % 2 == 0:
        l_arr.append(t)
    else:
        h_arr.append(t)

l_arr.sort()
h_arr.sort()

answer, answer_cnt = sys.maxsize, 0

# 어쨌든 모든 높이는 순차탐색을 해야함
for i in range(1, h+1):
    l_cnt = check(i-1, l_arr)
    h_cnt = check(h-i, h_arr)
    cur_cnt = l_cnt + h_cnt

    if cur_cnt < answer:
        answer = cur_cnt
        answer_cnt = 1
    elif cur_cnt == answer:
        answer_cnt += 1
    else:
        pass

print(answer, answer_cnt)

테스트 케이스

#input
20 10
5
5
6
4
6
7
9
1
4
4
9
4
9
3
7
1
5
1
6
5

# output
10 9

---

#input
6 5
1
3
4
2
2
3

# output
2 1