백준 #3020 개똥벌레

문제 링크

[3020 개똥벌레]

문제 설명

개똥벌레가 석순(아래에서 위로 나는 것)과 종유석(위에서 아래로 나는 것)으로 가득찬 동굴에 들어갔다. 동굴의 길이는 $N$미터이고 높이는 $H$미터이다. 석순과 종유석이 번갈아 가면서 나타 날 때 개똥벌레가 최소한으로 파괴하는 장애물의 개수를 구하는 문제

코드

import sys
input = sys.stdin.readline


N, H = map(int, input().split())
heights = [int(input()) for _ in range(N)]
up = [0] * (H + 1)
down = [0] * (H + 1)
for i in range(N):
    if i % 2 == 0:
        up[heights[i]] += 1
    else:
        down[H - heights[i] + 1] += 1

for i in range(H - 1, 0, -1):
    up[i] += up[i + 1]
for i in range(1, H + 1):
    down[i] += down[i - 1]
res = [0] * (H + 1)
for i in range(H + 1):
    res[i] = up[i] + down[i]
min_v = min(res[1:])
print(min_v, res[1:].count(min_v))

풀이

길이가 $H+1$인 석순과 종유석의 배열을 만들어주었다. 석순과 종유석이 자란 길이에 해당하는 인덱스를 1씩 더해준다. 석순의 경우는 아래에서 위로 자라기 때문에 가장 먼쪽 부터 앞쪽으로 오면서 누적으로 더해주고 종유석의 경우는 앞쪽부터 뒤쪽으로 가면서 누적으로 더해준다. 최종적으로 석순과 종유석을 합쳐주고 가장 작은 값을 구하고 작은값의 등장 횟수를 찾아주면 끝!