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

문제

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

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

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define INF 2000000000 // 20억
long long n;
long long seg[1000001];
long long x, ans;
long long h[100001];

int init(int node, int s, int e)
{
	if (s == e) return seg[node] = s; // start 와 end 의 위치가 일치하면 인덱스 s 값을 넣어준다.
	int mid = (s + e) / 2;
	int left_index = init(2 * node, s, mid);
	int right_index = init(2 * node + 1, mid + 1, e);

	return seg[node] =
		h[left_index] < h[right_index] ? left_index : right_index;
}

int query(int node, int s, int e, int l, int r) 
{
	if (e < l || r < s) return INF; // 찾아야하는 구간과 노드구간이 겹치지 않을 때
	if (l <= s && e <= r) return seg[node]; // 찾아야하는 구간내에 노드구간이 포함될 때
	int mid = (s + e) / 2;
	int left_index = query(2 * node, s, mid, l, r);
	int right_index = query(2 * node + 1, mid + 1, e, l, r);

	// 찾아야하는 구간이 노드구간에 포함되거나, 부분적으로 겹치는 경우
	if (left_index == INF) return right_index; // 에러방지
	else if (right_index == INF) return left_index; // 에러방지
	else return h[left_index] < h[right_index] ? left_index : right_index;
}


void solve(long long left, long long right)
{
	if (left > right) return;

	// 구간내의 최소값과 해당 인덱스 찾기
	long long index = query(1, 0, n - 1, left, right); // 구간 내의 최소값 찾기

	ans = max(ans, h[index] * (right - left + 1));

	solve(left, index - 1);
	solve(index + 1, right);

}

int main()
{
	while (1)
	{
		ans = 0;
		cin >> n;
		if (n == 0) break;

		for (int i = 0; i < n; i++)
		{
			cin >> h[i];
		}
		init(1, 0, n - 1); // 세그먼트 트리 만들기
		solve(0, n - 1);

		cout << ans << endl;
	}

}

 

1725번 히스토그램 문제와 6549번 히스토그램에서 가장 큰 직사각형 문제는 출력 형식만 다른 동일한 문제입니다.

 

둘 다 스택 혹은 분할 정복으로 풀이할 수 있는데 스택을 이용한 풀이법이 궁금하신분은 아래의 링크를 참고해주세요!

cocoon1787.tistory.com/315

[C/C++] 백준 1725번 - 히스토그램 (스택 풀이)

 

 

 

풀이 방법

구간내의 가장 낮은 막대의 길이와 인덱스를 찾고 분할 정복으로 최댓값을 찾았습니다. 처음에는 구간 내의 가장 낮은 막대기와 인덱스를 for문을 통해서 구하였는데 시간 초과가 발생하여 알아본 결과 세그먼트 트리를 사용하여야 한다는 것을 알게 되었습니다.

cocoon1787.tistory.com/313

[자료구조] 세그먼트 트리(구간트리, Segment Tree)로 구간 내 최소값 찾기

 

위의 포스팅에서 세그먼트 트리는 각 세그먼트 노드에 최솟값들을 저장하였지만 이번 문제를 풀 때는 세그먼트 트리에 최솟값이 아닌 최솟값의 인덱스를 저장하였습니다.

 

코드를 설명하자면 init함수는 입력 배열로 세그먼트 트리를 만들고, query함수는 구간 내의 최소값의 인덱스를 구합니다. 그리고 solve함수로 분할 정복을 하면서 정답을 구하게 됩니다.

 

예제 입력 1로 푸는 과정을 설명드리자면,

INDEX	0	1	2	3	4	5	6
h[ ]	2	1	4	5	1	3	3

입력이 h = {2, 1, 4, 5, 1, 3, 3}으로 주어졌을 때 init함수로 만들어지는 세그먼트 트리는 아래와 같습니다.

int init(int node, int s, int e)
{
	if (s == e) return seg[node] = s; // start 와 end 의 위치가 일치하면 인덱스 s 값을 넣어준다.
	int mid = (s + e) / 2;
	int left_index = init(2 * node, s, mid);
	int right_index = init(2 * node + 1, mid + 1, e);

	return seg[node] =
		h[left_index] < h[right_index] ? left_index : right_index;
}

각각의 노드에는 자식 노드들 중에서의 h의 최솟값 인덱스 정보를 담고 있습니다. 예를 들어 seg[2]에 적힌 1의 의미는 구간 (0~2) 사이의 배열 값들 중에서 최솟값의 인덱스는 1이라는 뜻입니다. 

 

그리고 query함수로 구간이 주어질 때 최소값의 인덱스를 찾을 수 있습니다.

int query(int node, int s, int e, int l, int r) 
{
	if (e < l || r < s) return INF; // 찾아야하는 구간과 노드구간이 겹치지 않을 때
	if (l <= s && e <= r) return seg[node]; // 찾아야하는 구간내에 노드구간이 포함될 때
	int mid = (s + e) / 2;
	int left_index = query(2 * node, s, mid, l, r);
	int right_index = query(2 * node + 1, mid + 1, e, l, r);

	// 찾아야하는 구간이 노드구간에 포함되거나, 부분적으로 겹치는 경우
	if (left_index == INF) return right_index; // 에러방지
	else if (right_index == INF) return left_index; // 에러방지
	else return h[left_index] < h[right_index] ? left_index : right_index;
}

왼쪽 자식 노드, 오른쪽 자식 노드로 재귀적으로 들어가면서 각각의 노드들은 자식 노드들 중에서 더 작은 값을 가지는 인덱스를 반환합니다. 

 

히스토그램

void solve(long long left, long long right)
{
	if (left > right) return;

	// 구간내의 최소값과 해당 인덱스 찾기
	long long index = query(1, 0, n - 1, left, right); // 구간 내의 최소값 찾기

	ans = max(ans, h[index] * (right - left + 1));

	solve(left, index - 1);
	solve(index + 1, right);

}

solve함수는 left와 right를 파라미터로 받고 left~right 구간 내의 최솟값의 index를 query함수로 구합니다. 그리고 해당 구간 길이를 가로길이로 하는 직사각형의 최대 크기는 (구간 내에서 가장 낮은 막대기 높이) * (구간 길이)가 됩니다. 

그리고 구간 내에서 가장 낮은 막대기의 인덱스는 1입니다. (4도 있지만 상관없습니다.)

따라서 분할 정복을 하기 위해 인덱스 1을 기준으로 양쪽으로 나눕니다.

왼쪽 도형의 경우 넓이를 구한 뒤 함수가 종료되고 오른쪽 도형은 다시 구간 내의 가장 낮은 막대기 높이의 인덱스를 찾아 넓이를 구한 뒤 다시 분할 정복을 하게 됩니다.

해당 구간에서 최솟값의 인덱스는 4이므로 넓이를 구한 뒤 인덱스 4를 기준으로 다시 양쪽으로 분할됩니다.

이런 식으로 구간들의 최대 넓이를 구하면서 모든 solve함수들이 종료되면 ans값에는 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이가 저장되게 됩니다.

 

 

 

 

 

<2021.03.27 스택 풀이 추가>

#include<iostream>
#include<algorithm>
#include<memory.h>
#include<vector>
using namespace std;

int N;
long long ans, h[100002];
vector<int> v;

int main() 
{

	while (true)
	{
		cin >> N;

		if (N == 0) break;

		for (int i = 1; i <= N; i++) cin >> h[i];

		v.push_back(0);
		for (int i = 1; i <= N + 1; i++)
		{
			while (!v.empty() && h[v.back()] > h[i])
			{
				int check = v.back();
				v.pop_back();
				ans = max(ans, h[check] * (i - v.back() - 1));
			}
			v.push_back(i);
		}

		cout << ans << '\n';

		// 초기화
		v.clear();
		ans = 0;
		memset(h, 0, 100000);
	}

}

 

 

 

 

 

<대회에서 공개된 문제 TC 리스트(반례)>

www.informatik.uni-ulm.de/acm/Locals/2003/input/histogram.in

 

 

 

 

 

www.acmicpc.net/problem/6549

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