1/24 Coding Test

✅ Coding Test

🎈 3020 개똥벌레

개똥벌레 한 마리가 장애물(석순, 종유석)으로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고 높이는 H미터이다. (N은 짝수), 첫 장애물은 항상 석순이고 그 다음에는 종유석과 석순이 번갈아가며 등장한다.

개똥벌레는 장애물을 피하지 않고 일직선으로 지나가며 모든 장애물을 파괴한다.
결과적으로 동굴 크기, 높이, 모든 장애물의 크기가 주어질 때, 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하는 문제.

import sys
input = sys.stdin.readline

n, h = map(int, input().split())
seok = []
jong = []
for i in range(n):
    if i % 2 == 0:
        seok.append(int(input()))
    else:
        jong.append(int(input()))

seok.sort()
jong.sort()

def binary_search(array, target):
    start, end = 0, len(array)
    while start < end:
        mid = (start + end-1) // 2
        if array[mid] <= target:
            start = mid + 1
        else:
            end = mid
    return len(array) - end

answer = n
cnt = 0

for i in range(1, h+1):
    seok_cnt = binary_search(seok, i-1)
    jong_cnt = binary_search(jong, h-i)
    if answer > seok_cnt + jong_cnt:
        answer = seok_cnt + jong_cnt
        cnt = 1
    elif answer == seok_cnt + jong_cnt:
        cnt += 1

print(answer, cnt)

< 해설 >

누적합이 아닌 이분탐색 방식으로 해결하기 위해 시간 투자를 오래 한 문제.
떠올린 아이디어로는 석순은 밑에서 시작, 종유석은 위에서 시작하기에 이를 고려해줘야 한다.
개똥벌레가 n길이의 동굴을 통과하는데 있어 방법은 총 h개다.
그렇기에 h번 만큼의 loop를 돌며 석순, 종유석의 upper bound를 확인해야 하는데, 석순과 종유석의 시작 위치가 다르기 때문에 이를 맞춰줄 필요가 있다.
h번 루프를 돌려 각 석순, 종유석의 upper bound를 구해 통과하는 장애물 개수를 구해주고 이를 비교해가며 answer (장애물 최소 통과 개수), cnt(h번 중 answer 만큼 통과하는 횟수)를 구한다.