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

2020-04-02 · 배운 것 · 5분 읽기

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

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

1. 풀이방법

이 문제의 풀이방법은 세가지이다.

1) 세그먼트 트리를 이용하여 최소높이, 최소높이 인덱스를 빠르게 찾아 푸는법
2) stack을 이용한 풀이
3) 종만북의 분할정복만을 이용한 풀이 (밑의 url참고)
https://blog.fxjodo.com/blog/71/

알고스팟_울타리 잘라내기_ 분할정복

2)번으로 풀어보려고 시도를 해보았으나 개념자체가 이해가 안되서 1)번으로 푼 풀이만 설명하겠다.

위의 그림처럼 세가지를 더이상 쪼갤수 없을때까지 반복해서 하면 된다.
1. 최소높이와 그 인덱스를 받는다.
2. (최소높이 * 범위)를 구해 지금까지 구한 넓이중에서 최대인지 비교해서 넣는다.
3. 범위를 왼쪽, 오른쪽으로 잘라 양쪽을 다시 1로 보낸다.

2. 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

//높이, 인덱스
vector<pair<int, int>> tree;
vector<int> arr;

pair<int, int> compareHeight(pair<int, int>a, pair<int, int>b)
{
	if (a.first <= b.first)
		return a;
		
	return b;
}

pair<int, int> treeInit(int node, int start, int end)
{
	//리프 노드일때
	if (start == end)
		return tree[node] = make_pair(arr[start], start);

	int mid = (start + end) / 2;
	return tree[node] = compareHeight(treeInit(node * 2, start, mid), treeInit(node * 2 + 1, mid + 1, end));
}

pair<int, int>getMinHeightAndIdx(int node, int start, int end, int left, int right)
{
	//안겹칠때
	if (right < start || end < left)
		return make_pair(INT_MAX, INT_MAX);

	//완전히 겹칠때
	if (start <= left && right <= end)
		return tree[node];

	//애매할때
	int mid = (left + right) / 2;
	return compareHeight(getMinHeightAndIdx(node*2, start, end, left, mid), getMinHeightAndIdx(node * 2 + 1, start, end, mid+1, right));
}

long long result;
//Divide and conquer algorithm
void binarySearch(int start, int end, int left, int right)
{
	long long width = end - start + 1;
	pair<int, int> minHaI = getMinHeightAndIdx(1, start, end, left, right);
	long long place = width * minHaI.first;
	int minIdx = minHaI.second;
	result = max(place, result);

	//하나일때 return
	if (start >= end)
		return;

	/*cout << "최소높이 : " << minHaI.first << "idx : " << minIdx << '\n';*/

	binarySearch(start, minIdx-1, left, right);
	binarySearch(minIdx +1, end, left, right);
}

int main()
{
	while (1)
	{
		int n;
		cin >> n;

		if (n == 0)
			break;

		//트리 자리 할당
		tree.resize(n * 4);
		tree[0] = make_pair(0, 0);

		//arr 입력
		int value;
		for (int i = 0; i < n; i++)
		{
			cin >> value;
			arr.push_back(value);
		}

		//tree 초기화
		treeInit(1, 0, n - 1);

		//넓이를 구하는 분할정복ㄱㄱ

		binarySearch(0, n - 1, 0, n - 1);

		cout << result << '\n';
		
		//tree, arr, result 지워주기
		tree.clear();
		arr.clear();
		result = 0;
	}
	return 0;
}

3.후기

꽤나 어려웠고 이걸 풀기까지 공부할게 너무많았다.
나중에 스택으로도 한번 풀어봐야겠다.