[Baekjoon] 6549, 1725 - 히스토그램에서 가장 큰 직사각형(C++)

1.  문제

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

6549번: 히스토그램에서 가장 큰 직사각형

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

1725번: 히스토그램

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

2. 아이디어

다음 블로그의 내용을 참조하였다.

https://cocoon1787.tistory.com/314

[C/C++] 백준 6549번 - 히스토그램에서 가장 큰 직사각형 (분할 정복 & 세그먼트 트리, 스택 풀이)

전반적인 알고리즘 아이디어는 다음과 같다.

1. 다음 사진과 같이 히스토그램 그림이 있을 경우, 세그먼트 트리를 이용해 전체 구간에서 가장 작은 높이의 인덱스를 구한다.

2. 구간의 길이(ed - st + 1) * 가장 작은 히스토그램의 높이 값(heights[minIdx - 1])을 구해 현재까지의 가장 큰 넓이(maxSize)와 비교해 만약 그 넓이보다 크다면 maxSize를 갱신한다.

3. 가장 작은 높이의 인덱스(minIdx)를 기준으로, 히스토그램을 두 구간으로 나누고, 재귀함수로 각 구간별로 2. 의 과정을 반복한다.

4. 만약 구간을 쪼갰을 때 넓이를 구할 수가 없다면 (st > ed로 1인 히스토그램에서 쪼개지는 경우) return한다.

 

알고리즘이 매우 단순해 처음에는 이걸로 해결할 수 있을지 모르겠지만, 재귀를 반복하다 보면, 결국 그림에서 3, 4번째 히스토그램과 같이 큰 히스토그램만 있는 구간에서 3번째 히스토그램이 가장 작은 높이(4)이므로 4 * 2 = 8로 이를 이용해 구간에서의 넓이를 구하게 된다.

또한, 엄청 높은 히스토그램 하나가 있는 경우에도, 그 막대의 높이 * 구간의 길이(1) = 그 막대의 높이 와 같이 그 막대의 높이를 그대로 사용하므로, 문제를 해결할 수 있다.

3. 개선할 점 및 배운점

특정 구간에서의 특정 값이 필요한 경우 -> 세그먼트 트리 자료구조 사용

부분 문제의 해를 재귀적으로 구하는 것이 전체 문제의 해와 관련이 있는 경우 -> 분할정복 알고리즘 사용

4. 코드