[BOJ-6549] 히스토그램에서 가장 큰 직사각형 (C++)

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

 

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

 

문제 설명

 

 - 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다.

 

 - 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수 있다.

 

 -  각 테스트 케이스에 대하여 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하라.

 

---

 

입력 값

 

 - 입력은 테스트 케이스 여러 개로 이루어져 있다.

 

 - 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음 주어진다.

   ( 1 <= n <= 100,000 )

 

 - 그 다음 n 개의 정수 h1, ... hn ( 0 <= hi <= 1,000,000,000)이 주어진다.

  이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽 순서대로 주어진다.

 

 - 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 히스토그램의 최대 넓이를 구하는 문제이다.

 

 - 단순하게 생각해보면, 왼쪽에서 부터 시작하는 모든 히스토그램의 넓이를 살펴보면,

   모든 히스토그램의 넓이를 알 수 있다.

 

 - 이 경우에는 시간 복잡도는 N+(N-1)+(N-2)+...+1 이 되기 떄문에 O($N^2$)이 된다.

    즉, 불가능해진다.

 

 - 그렇다면 어떻게 접근해야 할까?

 

 - 이 문제는 분할 정복으로 접근해야 한다.

 

 - 주어진 배열의 중간 값인 mid를 구한다.

 

 - 이때 주어진 배열에 의해 히스토그램을 만드는 경우 최대가 나오는 경우의 수는

 

 - start ~ mid 안에 있거나, mid+1 ~ last 안에 있거나 mid를 통과하는 것 중 하나이다.

 

 - 즉, 이 문제는 중간 값을 기준으로 나눈 두 부분과 중간 값을 지나는 히스토그램 중 최대를 찾으면 된다.

 

 - 두 부분으로 나누는 것이 logN, 다시 합치는 것이 logN이고

 

 - 합치는 과정에서 중간 값을 통과하는 히스토그램을 찾아야 하는 과정이 N이 소요된다.

 

 - 이 경우의 시간 복잡도는 O(NlogN)이 된다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

long long rec(int start, int last, vector<int> &v) {

	if (start == last) {
		return v[start];
	}

	long long result = 0;
	int mid = (start + last) / 2;

	int left = mid;
	int right = mid + 1;
	long long height = min(v[left], v[right]);
	result = height * 2;

	while (start < left || right < last) {
		long long now = 0;
		// 왼쪽 끝
		if (left == start) {
			right++;
			now = v[right];

		}
		// 오른쪽 끝
		else if (right == last) {
			left--;
			now = v[left];
		}
		// 다음 선택할 인덱스의 값 중 큰 값으로 이동한다.
		else if (v[left - 1] > v[right + 1]) {
			left--;
			now = v[left];

		}
		else {
			right++;
			now = v[right];
		}

		height = min(height, now);
		result = max(result, height*(right - left + 1));

	}

	result = max(result, rec(start, mid, v));
	result = max(result, rec(mid + 1, last, v));

	return result;


}

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

	int N, H;

	cin >> N;

	while (N != 0) {
		vector<int>v;
		for (int i = 0; i < N; i++) {
			cin >> H;
			v.push_back(H);
		}
		cout << rec(0, N - 1, v) << endl;
		cin >> N;
	}



	return 0;
}