[백준] 3020번 개똥벌레 (Python 파이썬) 누적합

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

3020번: 개똥벌레

지난번에 이분탐색(Binary Search)으로 풀었던 개똥벌레 문제

https://hongcoding.tistory.com/5

[백준] 3020번 개똥벌레 (Python 파이썬)

이 문제를 누적합 (전위합(Prefix Sum)) 으로 다시 풀었다.

높이 h부터 높이 1까지 누적 합을 계산하면 높이 i의 배열 값은 높이 i 이상의 모든 석순의 개수가 된다.

예를 들어, 높이가 6인 동굴에서 높이 5의 개똥벌레가 날아갈 때, 높이 5 이상의 석순에 모두 부딪히기 때문에

배열 5의 값이 높이 5의 개똥벌레가 부딪히는 석순의 개수가 된다.

 

마찬가지로 종유석은 위에서부터 내려오기 때문에 h - i + 1의 식을 이용하면 된다.

왜냐하면, 높이 6의 동굴에서 높이 2짜리 종유석은 높이 4 (실질적으로 3.5) 위로의 개똥벌레가 모두 부딪히기 때문이다.

즉, 석순처럼 높이2라고 해서 높이 2 밑의 개똥벌레가 부딪히는것이 아니라 위에서 부터기 때문에 반대가 된다.

 

파이썬 코드는 다음과 같다.

n, h = map(int, input().split())

down = [0] * (h + 1)  # 석순
up = [0] * (h + 1)  # 종유석

min_count = n  # 파괴해야 하는 장애물의 최소값
range_count = 0  # 최소값이 나타나는 구간의 수

for i in range(n):
    if i % 2 == 0:
        down[int(input())] += 1
    else:
        up[int(input())] += 1

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

for i in range(1, h + 1):

    if min_count > (down[i] + up[h - i + 1]):
        min_count = (down[i] + up[h - i + 1])
        range_count = 1
    elif min_count == (down[i] + up[h - i + 1]):
        range_count += 1

print(min_count, range_count)

모르시는 부분이 있으시면 언제든지 댓글 남겨주세요!

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !