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

문제 링크입니다. https://www.acmicpc.net/problem/6549

 

세그먼트 트리를 이용해 푸는 문제입니다.

 

N개의 직사각형의 높이가 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제입니다.

 

직사각형의 높이가 다를수 있기에, 붙어있는 직사각형들의 가장 높은 높이는 가장 직사각형의 높이가 될 것입니다.

따라서, 이를 이용해 세그먼트 트리로 풀었습니다.

 

먼저, 트리에 가장 작은 높이의 위치를 저장해줬습니다.

예를 들어, 자식 노드가 (2, 1)이라면, 1이 작은 높이이니 해당 노드는 높이가 1인 위치가 저장될 것입니다.

 

이렇게 트리에 작은 높이들의 위치가 저장이 되었다면,  (0 ~ N-1) 범위에서 가장 넓이가 넓은 직사각형을 찾습니다.

방법은 주어진 범위에서 가장 낮은 높이의 위치를 찾습니다. 

해당 위치가 찾아졌다면, 해당하는 높이 값을 기준으로 넓이를 구합니다.

-> 다음 탐색은 해당 위치를 기준으로 ±1의 값을 탐색합니다.(해당 높이는 탐색이 됐음으로 pass)

     2개로 나눠진 직사각형의 가장 높은 넓이를 구했다면 3개의 값을 비교해 가장 큰 넓이를 찾아줍니다.

---> 해당 과정을 반복하면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#define INF LLONG_MAX

using namespace std;

int N;
long long Index[100001];
vector<long long> Tree;

long long segment_tree(int st, int fin, int node) {
	// Index 값이 아닌 위치를 저장한다.
	if (st == fin) return Tree[node] = st;
	int mid = (st + fin) / 2;
	long long left = segment_tree(st, mid, node * 2);
	long long right = segment_tree(mid + 1, fin, node * 2 + 1);
	if (Index[left] > Index[right]) return Tree[node] = right;
	else return Tree[node] = left;
}

long long Find_height(int st, int fin, int left, int right, int node) {
	if (left > fin || right < st) return INF;
	if (left <= st && right >= fin) return Tree[node];
	int mid = (st + fin) / 2;
	long long left_height = Find_height(st, mid, left, right, node * 2);
	long long right_height = Find_height(mid + 1, fin, left, right, node * 2 + 1);
    	// INF가 나올 경우는 오류가 생기니 무조건 다른 쪽의 값을 return 해준다.
	if (left_height == INF) return right_height;
	if (right_height == INF) return left_height;
	if (Index[left_height] > Index[right_height]) return right_height;
	else return left_height;
}

long long Find_histogram(int left, int right) {
	if (left > right) return 0;
	long long height = Find_height(0, N - 1, left, right, 1);
	long long area = Index[height] * (right - left + 1);
	long long child_node = max(Find_histogram(left, height - 1), Find_histogram(height + 1, right));
	return max(area, child_node);
}

void solve() {
	int height = ceil(log2(N));
	Tree.resize((1 << (height + 1)));
	segment_tree(0, N - 1, 1);
	cout << Find_histogram(0, N - 1) << "\n" ;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	while (1) {
		cin >> N;
		if (N == 0) break;
		for (int i = 0; i < N; i++) scanf("%lld", &Index[i]);
		solve();
	}
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.