[1725] 히스토그램

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

세그먼트트리로 접근한 문제다. 

 

풀이

구간 최솟값의 인덱스를 반환하는 세그먼트트리를 생성한다. 0~N-1 범위의 최소 인덱스를 찾은 뒤, 해당 인덱스를 사용하여 히스토그램의 넓이를 계산, 이후 해당 [0 ~ 최솟값인덱스-1] 범위와 [최솟값 인덱스+1 ~ N-1] 범위의 히스토그램 넓이를 계산해 나가면 된다. 

예제 [2,1,4,5,1,3,3]을 기준으로 다음과 같이 동작한다.

 

최솟값 인덱스 세그먼트트리 생성

 

가장 먼저 0~6 전체 범위의 히스토그램 영역을 탐색한다.

1번 인덱스가 반환되며 해당 블록의 높이인 1과 밑변에 해당하는 0~6 범위(6-0+1)를 곱해 넓이를 계산한다.

 

이후 해당 최소값 인덱스를 기준으로 좌, 우 영역의 넓이를 계산해 나가면 된다.

좌측의 경우 2*1 = 2가 반환되며 우측의 경우 1*5 = 5가 계산된다. 

이후 좌측의 경우 범위의 시작값과 마지막값이 동일하므로 종료.

우측의 경우 아직 탐색할 범위가 남았으므로 좌측과 우측을 계산한다.

 

2~3에 해당하는 넓이 4*2 = 8 계산. 5~6에 해당하는 넓이 3*2 = 6 계산.

남은 범위 계산을 위해 재귀호출을 이어간다.

 

3~3 범위 1*5 = 5 계산. 6~6 범위 3*1 = 3 계산.

더 이상 탐색할 범위가 없으므로 앞서 나온 모든 값들 중 최대값 8을 출력하면 정답이다.

 

정답 코드