[백준] 히스토그램 (1725번)

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입력 1 복사

7 2 1 4 5 1 3 3

예제 출력 1 복사

8

---

유명한 히스토그램 문제다.

알고스팟의 FENCE, 백준의 히스토그램에서 가장 큰 직사각형 문제와 비슷한 문제다.

내 블로그에 저 두 문제에 대한 포스트를 이미 올렸으니 참고해도 좋다.

 

분할정복을 하는 방법, 스택을 이용하는 방법 등 여러가지 해결 방법이 있으나, 

내겐 세그먼트 트리를 이용하는 방법이 가장 이해가 잘 됐다.

 

세그먼트 트리를 이용하는 방법은, 각 구간별로 최소 높이를 갖는 인덱스를 저장하게 하는 것이다.

예제를 생각해보면 (0, N-1) 범위에서의 최소 높이를 갖는 인덱스는 1 또는 4이다. 

이 인덱스를 통해 높이를 구하고 가로 길이를 곱해서 직사각형 넓이를 구하고, 이 인덱스를 기준으로 좌, 우로 나눠 다시 넓이를 구하는 식으로 모든 가능한 직사각형의 넓이를 구하는 것이다.

따지고보면 분할정복이라고 할 수도 있다.

 

아래 코드의 init과 query 함수는 세그먼트 트리에 대한 지식이 있다면 충분히 이해할 수 있을 것이다.

답을 구하는 solve 함수는 말한대로 분할 정복을 하는 함수이다.

(left, right) 범위로 만들 수 있는 직사각형의 최대 넓이를 구해서 반환한다. 

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/bebc3c7f253fe8f425ef7a8a340730d6f9cc35bc/BaekJoon/2020/%ED%9E%88%EC%8A%A4%ED%86%A0%EA%B7%B8%EB%9E%A8%20(1725%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int N;
int p[100001];
vector<int> range;

int init(int left, int right, int node) {
	if (left == right) return range[node] = left; // 인덱스를 저장

	int mid = (left + right) / 2;
	int lo = init(left, mid, node * 2);
	int hi = init(mid + 1, right, node * 2 + 1);

	if (p[lo] <= p[hi]) return range[node] = lo; // 구간 내에 최소값을 가지는 인덱스를 저장
	else return range[node] = hi;
}

int query(int left, int right, int node, int nodeLeft, int nodeRight) {
	if (left <= nodeLeft && nodeRight <= right) return range[node]; // 구하는 범위 내에 있을 경우 반환
	if (nodeRight < left || right < nodeLeft) return -1; // 범위 벗어나면 -1

	int mid = (nodeLeft + nodeRight) / 2;
	int lo = query(left, right, node * 2, nodeLeft, mid); // (nodeLeft, mid) 사이의 최소값 인덱스
	int hi = query(left, right, node * 2 + 1, mid + 1, nodeRight); // (mid+1, nodeRight) 사이의 최소값 인덱스

	if (lo == -1) return hi; 
	if (hi == -1) return lo;
	if (p[lo] <= p[hi]) return lo; // 최소값을 갖는 인덱스 반환.
	else return hi;
}

ll solve(int left, int right) {
	if (left > right) return -1; // 종료조건

	int loIdx = query(left, right, 1, 0, N - 1); // (left,right) 범위의 최소값을 갖는 인덱스 구하기
	ll res = (ll)((ll)right - (ll)left + 1) * p[loIdx]; // (left, right) 범위를 모두 포함하게 만들 수 있는 직사각형 넓이

	if (loIdx != left)
		res = max(res, solve(left, loIdx - 1)); // (left, loIdx-1) 까지 범위로 만들 수 있는 직사각형의 최대 넓이 최신화
	if (loIdx != right) 
		res = max(res, solve(loIdx + 1, right)); // (loIdx+1, right) 범위
	
	return res; // 최대 넓이 반환
}

int main()
{
	cin >> N;
	range.resize(N * 4);
	for (int i = 0; i < N; i++)
		cin >> p[i];
	
	init(0, N - 1, 1); // 세그먼트 트리 초기화
	
	cout << solve(0, N - 1); // 정답 출력
}