개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.
아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)
이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)
하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.
동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)
다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.
출력
첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.
풀이
이 문제는 누적합 방식으로 매우 간단하게 해결할 수 있습니다. 기본적으로 개똥벌레가 날아가는 구간의 장애물 개수를 알아야 무엇이든 시작할 수 있는데요. 홀수번에는 석순이 나옵니다. 석순은 바닥에서부터 높이만큼 자라고, 짝수번에 나타나는 종유석은 천장에서 높이만큼 아래로 내려옵니다.
여기서 생각한 아이디어는 밑에서부터 누적합으로 개똥벌레가 지나갈 구간의 충돌지점의 수를 구할 수 있다는 것입니다. 먼저 구간별 충돌횟수를 기록할 수 있는 배열을 선언하겠습니다. 가장 밑에 구간부터 석순은 높이까지 계속 충돌할 수 있게 자라겠죠. 그리고 종유석은 중간중간에 등장할 것입니다. 그래서 종유석의 등장점과 석순의 밑 바닥은 1로 두어 누적합을 실행하면 구간 별 개똥벌레의 충돌횟수를 구할 수 있게 됩니다.
다만, 석순이 끝나는 지점은 구간에 포함되지 않아야 하기 때문에 끝점에는 -1로 둡니다. 그렇게 누적합을 실행하면 배열의 최소값이 개똥벌레의 최소 충돌횟수가 될 것입니다.
import sys
input = sys.stdin.readline
n, h = map(int, input().split())
# 구간별 충돌 횟수 기록 배열
lines = [0] * h
# 입력
for i in range(n):
size = int(input())
# 종유석이라면
if i % 2 == 0:
lines[h-size] += 1
# 석순이라면
else:
lines[0] += 1
lines[size] -= 1
# 구간합 실행
for i in range(1, h):
lines[i] += lines[i-1]
# 최소충돌횟수 등장 횟수 기록
result = 0
# 최소충돌횟수는 최소값
low = min(lines)
for l in lines:
# low와 같다면 횟수 증가
if l == low:
result += 1
# 정답 출력
print(low, result)
