[백준] 1725 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

 

 

세그먼트 트리를 활용한 문제입니다.

1.세그먼트 트리를 다음과 같이 만듭니다

 각 노드는 그 노드가 포함하는 범위의 직사각형의 높이 중 가장 낮은 높이의 인덱스를 가집니다.

int init(int l,int r,int n) {
	if (l == r) {
		seg[n] = l;
		return hi[l];
	}
	int mid = (l + r) / 2;
	int le = init(l, mid, n * 2), ri = init(mid + 1, r, n * 2 + 1);
	if (le <= ri) {
		seg[n] = seg[n * 2];
		return le;
	}
	else {
		seg[n] = seg[n * 2 + 1];
		return ri;
	}
}

 

2.분할정복을 이용해 가능한 넓이로 쪼개갑니다.

 2-1. 범위 내 가장 낮은 높이의 인덱스를 기준으로 높이*범위 길이

 2-2. 범위 내 가장 낮은 높이의 인덱스 왼쪽을 분할정복

 2-3. 범위 내 가장 낮은 높이의 인덱스 오른쪽을 분할정복

int find(int l,int r) {
	if (l == r) {
		return ans = max(ans, hi[l]);
	}
	int idx = query(1,N,l,r,1); //l과r 범위내 최소높이를 가지는 인덱스
	ans = max(ans, hi[idx] * (r - l + 1));
	if (l != idx)
		ans = max(ans, find(l, idx - 1));
	if (r != idx)
		ans = max(ans, find(idx + 1, r));
	return ans;
}

이때 사용하는 가장 낮은 높이의 인덱스를 찾는 쿼리는 다음과 같습니다.

int query(int l, int r, int s, int t, int n) {
	if (r < s || t < l)return 0;
	if (s <= l && r <= t)return seg[n];
	int mid = (l + r) / 2;
	int le = query(l, mid, s, t, n * 2);
	int ri = query(mid + 1, r, s, t, n * 2 + 1);
	if (hi[le] <= hi[ri]) {
		return le;
	}
	else {
		return ri;
	}
}

이때 범위 밖으로 나가는경우 널 값이 필요하기때문에 0으로 저장하고, hi[0]에 쓰레기값을 저장했습니다.

코드 전문은 다음과 같습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, h, hi[100001], seg[400004], ans = -1;

int init(int l,int r,int n) {
	if (l == r) {
		seg[n] = l;
		return hi[l];
	}
	int mid = (l + r) / 2;
	int le = init(l, mid, n * 2), ri = init(mid + 1, r, n * 2 + 1);
	if (le <= ri) {
		seg[n] = seg[n * 2];
		return le;
	}
	else {
		seg[n] = seg[n * 2 + 1];
		return ri;
	}
}
int query(int l, int r, int s, int t, int n) {
	if (r < s || t < l)return 0;
	if (s <= l && r <= t)return seg[n];
	int mid = (l + r) / 2;
	int le = query(l, mid, s, t, n * 2);
	int ri = query(mid + 1, r, s, t, n * 2 + 1);
	if (hi[le] <= hi[ri]) {
		return le;
	}
	else {
		return ri;
	}
}
int find(int l,int r) {
	if (l == r) {
		return ans = max(ans, hi[l]);
	}
	int idx = query(1,N,l,r,1); //l과r 범위내 최소높이를 가지는 인덱스
	ans = max(ans, hi[idx] * (r - l + 1));
	if (l != idx)
		ans = max(ans, find(l, idx - 1));
	if (r != idx)
		ans = max(ans, find(idx + 1, r));
	return ans;
}
int main() {
	FAST;
	hi[0] = INT_MAX;
	cin >> N;
	REP(i, N)
		cin >> hi[i];
	init(1,N,1);
	find(1, N);
	cout << ans;
}