https://www.acmicpc.net/problem/3020
문제 풀이
문제를 보자마자 딱 이분탐색(떡 자르기 등) 풀이법이 떠올랐다. 근데 지금은 누적합을 공부중이기 때문에 누적합으로 풀어보고자 했다! 처음에는 n * h 배열을 만들어서 횡단으로 하나씩 봐야하나 했지만 인터넷에 좋은 풀이가 있어 공부해보기로 했다.
이 문제는 말보다 그림으로 보는게 더 이해갈것 같아서 그려가면서 이해했다. 종유석은 왜 H - h + 1 순으로 저장되냐 하면, 보시다싶이 거꾸로 되어있어서다.
따라서 처음에는 해당 높이의 석순, 종유석을 저장한다. 짝수 인덱스에는 석순을, 홀수 인덱스에는 종유석을 저장한다.
그 다음, 저장된 데이터를 갖고 누적합을 진행한다. 누적합을 사용하는 이유는 만약 석순의 최대 높이가 7이라면, 7이하로 장애물이 걸리기 때문이다.
그 다음 누적합한 데이터를 갖고 문제에서 요구하는 최소 장애물 개수와 구간의 수를 구하면 된다!
code
n, h = map(int, input().split())
bottom = [0 for _ in range(h + 1)]# 석순
up = [0 for _ in range(h + 1)]# 종유석
answer = [n, 0] #최소, 구간개수
for i in range(n):
height = int(input().strip())
if i % 2 == 0:# 짝수면 아래
bottom[height] += 1
else:# 홀수면 위쪽 장애물
up[h - height + 1] += 1
for i in range(1, h+1):
up[i] += up[i - 1]
bottom[h - i] += bottom[h - i + 1]
for i in range(1, h+1):
if answer[0] > bottom[i] + up[i]:# 최솟값 갱신
answer[0] = bottom[i] + up[i]
answer[1] = 1
elif answer[0] == bottom[i] + up[i]:
answer[1] += 1
print(*answer)
