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

3020.개똥벌레

 

• 누적합 
  • 구간 update 후 get
  • 시작점에 +1, 끝점에 -1 한 뒤 전체 누적합
  • n=14, h=5 일때 구간을 0~6 (h+1) 구간까지 두고,
    • 석순 길이가 1이면 1만 해당하므로 1에 +1, 2에 -1
    • 종유석 길이가 2이면 4,5가 해당하니까 4에 +1, 6에 -1
    • 이후 누적합은 1~h 구간만 살펴볼 것

n, h = map(int, input().split())
lst = [0 for _ in range(h+2)]
for i in range(n):
    x = int(input())
    if i % 2 == 0:  # 석순
        lst[1] += 1
        lst[x+1] -= 1
    else:  # 종유석
        lst[h-x+1] += 1
        lst[h+1] -= 1

for i in range(1, h+1):
    lst[i] += lst[i-1]

min_value = min(lst[1:-1])
min_count = lst[1:-1].count(min_value)
print(min_value, min_count)