[G5] 백준 3020 - 개똥벌레 (Python3)

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

---

 

문제 설명

높이가 HHH일 때, 몇 개의 벽을 뚫어야 하는지 계산하고,
그중에서 최소로 뚫을 수 있는 횟수와 그런 높이가 몇 개인지 구하는 문제이다.

해결 방법은 크게 두 가지로 나뉜다.

1. 누적합(Prefix Sum) 활용
2. 이분 탐색(Binary Search) 활용

---

해결 방법 1: 누적합(Prefix Sum)

누적합을 사용하면 높이별로 벽을 뚫어야 하는 개수를 빠르게 계산할 수 있다.

알고리즘 설명

1. 석순(아래에서 위로 솟는 기둥)과 종유석(위에서 내려오는 기둥)을 나눈다.
2. 종유석 높이를 변환하여 H - 종유석 길이 + 1 형태로 정리
3. 석순과 종유석의 누적합 배열을 만든다.
4. 각 높이별로 벽을 뚫어야 하는 개수를 계산하여 최소값을 찾는다.

💻 코드 (누적합)

# 3020 개똥벌레_누적합
N, H = map(int, input().split())

# 종유석, 석순
stalactites, stalagmites = [], []
for i in range(N):
    if i%2 == 0:
        stalagmites += [int(input())]
    else:
        stalactites += [int(input())]

# 종유석 전처리
for i in range(len(stalactites)):
    stalactites[i] = H - stalactites[i] + 1

# 종유석에 대한 누적합 (이 이상에서 벽을 뚫는다.)
prefix = [0] * (H+1)
for elem in stalactites:
    prefix[elem] += 1
for i in range(H):
    prefix[i+1] += prefix[i]


# 석순에 대한 누적합 (이 이하에서 벽을 뚫는다.)
prefix_reverse = [0] * (H+1)
for elem in stalagmites:
    prefix_reverse[elem] += 1
prefix_reverse.reverse()

for i in range(H):
    prefix_reverse[i+1] += prefix_reverse[i]
prefix_reverse.reverse()

# 정답 구하기
m, cnt = 10**7, 0

for i in range(1, H+1):
    if prefix[i] + prefix_reverse[i] < m:
        cnt = 1
        m = prefix[i] + prefix_reverse[i]
    elif prefix[i] + prefix_reverse[i] == m:
        cnt += 1
print(m, cnt)

---

해결 방법 2: 이분 탐색(Binary Search)

bisect 라이브러리를 활용하면 높이별 벽을 뚫는 개수를 빠르게 구할 수 있다.

알고리즘 설명

1. 석순과 종유석을 정렬
2. 각 높이별로 bisect를 이용해 벽을 뚫어야 하는 개수를 찾는다.
   • bisect_left() 를 이용해 석순을 몇 개 뚫어야 하는지 구함
   • bisect_right() 를 이용해 종유석을 몇 개 뚫어야 하는지 구함
3. 각 높이별 벽을 뚫어야 하는 개수를 계산하여 최소값을 찾는다.

💻 코드 (이분 탐색)

# 3020 개똥벌레_이분탐색
from bisect import bisect_left, bisect_right

N, H = map(int, input().split())

# 종유석, 석순
stalactites, stalagmites = [], []
for i in range(N):
    if i%2 == 0:
        stalagmites += [int(input())]
    else:
        stalactites += [int(input())]

# 종유석 전처리
for i in range(len(stalactites)):
    stalactites[i] = H - stalactites[i] + 1

# 종유석
stalactites.sort()
st = []
for h in range(1, H+1):
    st.append(bisect_right(stalactites, h))

# 석순
stalagmites.sort()
sm = []
for h in range(1, H+1):
    sm.append(len(stalagmites) - bisect_left(stalagmites, h))


# 정답 구하기
m, cnt = 10**7, 0
test = []
for i in range(H):
    test.append(st[i] + sm[i])
    if st[i] + sm[i] < m :
        cnt = 1
        m = st[i] + sm[i]
    elif st[i] + sm[i] == m:
        cnt += 1
print(m, cnt)

---

bisect 사용법 정리

bisect_left()

• 정렬된 배열에서 새로운 값(h)을 삽입할 최소 index를 반환
• 석순 개수를 구할 때 사용

석순 개수 = 전체 개수 - bisect_left(석순, h)

bisect_right()

• 정렬된 배열에서 새로운 값(h)을 삽입할 최대 index를 반환
• 종유석 개수를 구할 때 사용

종유석 개수 = bisect_right(종유석, h)

---

비교

해결 방법시간 복잡도특징

누적합	O(N+H)	한 번의 순회로 모든 높이의 벽 개수 계산
이분 탐색	O(Nlog⁡H)	정렬 후 bisect를 사용해 개수 탐색

• N이 클 경우(최대 200,000)에는 누적합이 더 효율적
• 이분 탐색도 직관적인 코드로 해결 가능

---

정리

누적합을 활용하면 한 번의 순회로 벽뚫기 개수를 계산할 수 있어 더 효율적이다.
하지만 이분 탐색도 bisect 모듈을 활용하면 간단하게 해결 가능하다.

입력 크기에 따라 최적의 방법을 선택하는 것이 중요하다! 🚀