[백준알고리즘] 3020번: 개똥벌레 -Python

[백준알고리즘] 3020번: 개똥벌레 -Python

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

3020번: 개똥벌레

@Crocus 님의 블로그의 글을 참고했다.

https://www.crocus.co.kr/886

 

Prefix Sum을 구하는 문제라고 한다.

 

처음에는 이분탐색, 삼분 탐색.. 이런 것들을 생각했다. 그런데 아무리 생각해도 석순과 종유석이 번갈아 나오는 상황에서 빠르게 두 높이를 모두 고려한 탐색법이 생각이 나지 않았다. 이래저래 생각을 했는데 참고했던 게 아쉽다!

 

석순과 종유석을 나눠서 생각한 다음에 두개를 합쳐서 조각의 개수를 세주었다.

석순과 종유석의 잘린 개수를 찾는 방법은 각각의 높이로 잘랐을 때 나오는 조각의 개수들을 기록해주는 방법이다. 여기서, 석순을 예로 들면 4로 잘랐을 때 나오는 조각의 개수는 높이가 4인 석순과 높이가 4보다 큰 석순의 개수이다. 이러한 방법을 적용해서 계산해주었다.

import sys
input = sys.stdin.readline

n, h = map(int, input().split())
# 높이가 i인 석순, 높이가 h-i+1인 종유석
down = [0] * (h+1); up = [0] * (h+1)
for i in range(n):
    if i%2:
        up[int(input())] += 1
    else:
        down[h-int(input())+1] += 1

# 각 높이로 잘랐을 때 생기는 조각의 개수
# i줄을 잘랐을 때 석순은 높이가 i인 석순의 개수와 i+1이상의 석순의 개수
for i in range(h-1, 0, -1):
    up[i] += up[i+1]
# i줄을 잘랐을 때 종유석의 위치가 i인 석순의 개수와 i-1이하에 위치한 종유석의 개수
for i in range(2, h+1):
    down[i] += down[i-1]

total = [0] * (h+1)
for i in range(1, h+1):
    total[i] = up[i] + down[i]

# 0번 인덱스 제외
res = total[1:]
v = min(res)
print(v, res.count(v))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다