백준 3020번: 개똥벌레 (Python)

접근

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

3020번: 개똥벌레

누적합을 이용해 높이 i 이상 석순의 개수, i 이상의 종유석의 개수를 저장해줍니다. 이 때, 종유석은 위서부터 아래로 내려온다는 점을 주의하여 풀어주면 문제를 해겷할 수 있습니다.

코드

import sys

input = sys.stdin.readline

N, H = map(int, input().split(" "))
down = [0] * (H + 1)
up = [0] * (H + 1)
min = N
num = 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 > (down[i] + up[H - i + 1]):
        min = down[i] + up[H - i + 1]
        num = 1
    elif min == (down[i] + up[H - i + 1]):
        num += 1

print(min, num)

더 생각해 볼 것?

개인적으로 누적합 문제인지 모르고 풀었다면 엄청 헤메었을 것 같은 문제였습니다. 문제의 유형을 한가지 배웠습니다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!