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

알고리즘 문제 전체 링크

 

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

 

참고

- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)

- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 10868 : 최솟값

 

 

문제의 예시대로 사각형을 그려보자.

 

전체 구간 [1 ~ 7]을 포함하는 가장 큰 직사각형의 넓이는 7이다.

 

예를 들어 구간 [6 ~ 7]만 포함하는 가장 큰 직사각형의 넓이는 6이 된다.

 

이 넓이는 어떻게 구할 수 있을까?

구간 [a ~ b]에서 가장 작은 높이와 (b - a + 1)을 곱하면 된다.

그리고 구간 [a ~ b]에서 가장 작은 높이의 index가 c라면

구간 [a ~ c - 1]과 구간 [c + 1 ~ b]로 나눈 후 같은 과정을 반복해서,

그 중 가장 큰 넓이를 매번 갱신하면 된다.

 

예를 들어 위의 경우는 [1 - 7] 구간에서 넓이 7을 구한 후,

구간 [1 - 1] / 구간 [3 -7]로 나누게 된다. (또는 구간 [1 - 4] / 구간 [6 - 7])

구간 [1 - 7]에서 가장 작은 높이를 가지는 index가 2이기 때문이다. (또는 5)

 

구간 중 가장 높이가 작은 index는 세그먼트 트리를 이용하여 저장하면 된다.

위의 예시를 트리로 그려보면 아래와 같다.

 

세그먼트 트리의 노드는 높이가 작은 index를 가지므로 isMin은 다음과 같이 정의한다. 

여기서 h는 문제에서 주어진 높이를 저장하는 배열이다.

int isMin(int a, int b)
{
	return (h[a] < h[b]) ? a : b;
}

 

그 외에는 BOJ 10868 : 최솟값과에서 사용한 방법과 같다. 

void update(int index, int value)
{
	index += start;

	while (index > 1)
	{
		tree[index] = isMin(tree[index], value);

		index /= 2;
	}
}

int getMinIndex(int left, int right)
{
	int ans = 0;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans = isMin(ans, tree[left]);
			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans = isMin(ans, tree[right]);
			right -= 1;
			right /= 2;
		}
	}

	if (left == right) ans = isMin(ans, tree[left]);

	return ans;
}

 

이때, ans가 0부터 시작해서 index를 찾기 때문에 main문 초반에 h[0]에는 최악의 값(가장 큰 값)을 넣어둔다.

h[0] = 1000000001;

 

이제 구간에서 가장 작은 높이를 가지는 index를 구할 수 있으므로,

getMaxArea를 아래와 같이 만들 수 있다.

minIndex를 기준으로 양 옆을 구한 후, 가장 큰 값을 갱신한다.

ll getMaxArea(int left, int right)
{
	if (left > right) return 0;

	int minIndex = getMinIndex(left, right);

	ll maxArea = h[minIndex] * (right - left + 1);

	ll leftMaxArea = getMaxArea(left, minIndex - 1);
	ll rightMaxArea = getMaxArea(minIndex + 1, right);

	if (maxArea < leftMaxArea) maxArea = leftMaxArea;
	if (maxArea < rightMaxArea) maxArea = rightMaxArea;

	return maxArea;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

typedef long long int ll;

int N;
ll h[100100];
int tree[100100 * 4];
int start;

int isMin(int a, int b)
{
	return (h[a] < h[b]) ? a : b;
}

void update(int index, int value)
{
	index += start;

	while (index > 1)
	{
		tree[index] = isMin(tree[index], value);

		index /= 2;
	}
}

int getMinIndex(int left, int right)
{
	int ans = 0;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans = isMin(ans, tree[left]);
			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans = isMin(ans, tree[right]);
			right -= 1;
			right /= 2;
		}
	}

	if (left == right) ans = isMin(ans, tree[left]);

	return ans;
}

ll getMaxArea(int left, int right)
{
	if (left > right) return 0;

	int minIndex = getMinIndex(left, right);

	ll maxArea = h[minIndex] * (right - left + 1);

	ll leftMaxArea = getMaxArea(left, minIndex - 1);
	ll rightMaxArea = getMaxArea(minIndex + 1, right);

	if (maxArea < leftMaxArea) maxArea = leftMaxArea;
	if (maxArea < rightMaxArea) maxArea = rightMaxArea;

	return maxArea;
}

int main()
{
	h[0] = 1000000001;

	int n;
	while (1)
	{
		scanf("%d", &N);

		if (N == 0) break;

		for (n = 1; (1 << n) <= N; n++);
		start = 1 << n;
		start--;

		int maxTreeIndex = (1 << (n + 1));

		for (int i = 1; i <= maxTreeIndex; i++) tree[i] = 0;
		for (int i = 1; i <= N; i++)
		{
			scanf("%lld", &h[i]);
			update(i, i);
		}

		printf("%lld\n", getMaxArea(1, N));
	}

	return 0;
}

---

탑 다운 방식은 다음과 같다.

getMinIndex에서 범위를 벗어나는 경우는 -1을 return한 후, 예외 처리를 해야한다.

#include <stdio.h>

typedef long long int ll;

int N;
ll h[100100];
int tree[100100 * 4];

int isMin(int a, int b)
{
	return (h[a] < h[b]) ? a : b;
}

int init(int left, int right, int node)
{
	if (left == right) return tree[node] = left;

	int mid = (left + right) / 2;

	return tree[node]
		= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}

int getMinIndex(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return -1;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	int leftIndex = getMinIndex(left, mid, a, b, node * 2);
	int rightIndex = getMinIndex(mid + 1, right, a, b, node * 2 + 1);

	if (leftIndex == -1) return rightIndex;
	if (rightIndex == -1) return leftIndex;

	return isMin(leftIndex, rightIndex);
}

ll getMaxArea(int left, int right)
{
	if (left > right) return 0;

	int minIndex = getMinIndex(1, N, left, right, 1);

	ll maxArea = h[minIndex] * (right - left + 1);

	ll leftMaxArea = getMaxArea(left, minIndex - 1);
	ll rightMaxArea = getMaxArea(minIndex + 1, right);

	if (maxArea < leftMaxArea) maxArea = leftMaxArea;
	if (maxArea < rightMaxArea) maxArea = rightMaxArea;

	return maxArea;
}

int main()
{
	while (1)
	{
		scanf("%d", &N);

		if (N == 0) break;

		for (int i = 1; i <= N * 3; i++) tree[i] = 0;
		for (int i = 1; i <= N; i++) scanf("%lld", &h[i]);

		init(1, N, 1);

		printf("%lld\n", getMaxArea(1, N));
	}

	return 0;
}