[acmicpc] 3020. 개똥벌레 (python)

구간합 알고리즘

import sys
input=sys.stdin.readline

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

down = [0] * h  # 석순
up = [0] * h  # 종유석

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

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

down.reverse()
result=[]
for j in range(len(down)):
    result.append(down[j]+up[j]) # 각 높이마다 장애물 합

mins=min(result)
cnt=result.count(mins)

print(mins,cnt)

---

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

3020번: 개똥벌레