[누적합] 백준 3020 개똥벌레

생각을 좀 다르게 가져야하는 문제

창의성이 필요했다. 

 

import sys
N, H = map(int, sys.stdin.readline().split())
up = [0]*(H+1)
down = [0]*(H+1)
# up[i] : 개똥벌레가 i(밑에서부터)로 날때 파괴해야하는 장애물 개수
for i in range(N):
    if i%2==0:
        up[int(sys.stdin.readline())]+=1
    else:
        down[int(sys.stdin.readline())]+=1
for i in range(H, 1, -1):
    up[i-1]+=up[i]
    down[i-1]+=down[i]
obs_min = N
for i in range(1, H+1):
    up[i] = up[i] + down[H-i+1]
    if obs_min>up[i]:
        obs_min = up[i]
print(obs_min, up[1:].count(obs_min))