[백준/BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형

www.acmicpc.net/problem/6549

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

분할 정복을 이용하여 문제를 해결하였다. 가운데 기준으로 왼쪽에서 얻어지는 가장 큰 값과, 오른쪽에서 얻어지는 가장 큰 값과 가운데에서 만들어지는 가장 큰 값을 비교하였다. 가운데에서 확장을 할 때는 더 큰 쪽으로 확장을 하였다.

 

코드

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

int n;
vector<int> input_data;

//분할정복 이용
//알고리즘 문제해결 전략1 책 분할정복 파트 공부 후 실습
long long Solve(int left, int right)
{
	if (left == right)
		return input_data[left] * 1;

	int mid = (left + right) / 2;

	long long ret = max(Solve(left, mid), Solve(mid + 1, right)); //왼쪽결과와 오른쪽 결과중 큰값

	//가운데 결과와 비교
	int check_left = mid;
	int check_right = mid + 1;
	int height = min(input_data[check_left], input_data[check_right]);
	while (1)
	{
		ret = max(ret, (long long)height*(check_right - check_left + 1));

		if (check_left == left && check_right == right)
			break;

		else if (check_left == left && check_right != right)
		{
			check_right++;

			height = min(height, input_data[check_right]);
		}

		else if (check_left != left && check_right == right)
		{
			check_left--;

			height = min(height, input_data[check_left]);
		}

		else if (check_left != left && check_right != right)
		{
			//높이가 더 큰쪽으로 확장을 한다
			if (input_data[check_left - 1] < input_data[check_right + 1])
			{
				check_right++;

				height = min(height, input_data[check_right]);
			}

			else
			{
				check_left--;

				height = min(height, input_data[check_left]);
			}
		}
	}

	return ret;
}



int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	while (1)
	{
		input_data.clear();

		cin >> n;

		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
		{
			int h;
			cin >> h;

			input_data.push_back(h);
		}

		cout << Solve(0, n - 1) << "\n";

	}



	return 0;
}