백준 3020번 개똥벌레

문제링크: https://www.acmicpc.net/problem/3020

사용한 알고리즘: 펜윅트리


높이가 5인 동굴을 생각해보면, 구간은 0.5 , 1.5 , 2.5 , 3.5 , 4.5 로 총 5개가 있습니다.
각 구간별로 갖는 장애물의 개수를 펜윅트리로 생각했습니다.
이에 따라 펜윅트리를 구현할 때, tree[1] = 0.5 구간, tree[2] = 1.5 구간 ... 등으로 생각했습니다. 천장을 0, 바닥을 H 의 높이로 생각해주었습니다.

각각의 입력에서 석순(바닥부터 자람)과 종유석(천장부터 자람)이 차지하는 구간들을 +1로 update 해주어 펜윅트리를 구성하였습니다. 예를들어 높이 5인 동굴에 석순이 3 크기이면,
이는 2초과 5미만인 구간, 즉 tree[3]: 2.5 , tree[4]: 3.5, tree[5]: 4.5 의 구간에 +1이 됩니다.
이후 1~H 의 구성된 구간중 최대값과, 개수를 찾아주었습니다.