https://www.acmicpc.net/problem/6549
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤
www.acmicpc.net
브루트포스로 O(N^2)으로 하면
100000 * 100000 -> 시간 초과
세그먼트 트리를 사용해야겠다.
세그먼트 트리에 저장하는 값은
해당 구간에서
"가장 작은 높이를 가진 배열의 인덱스"
1. 왜 인덱스?
구간을 나눠가면서 가장 큰 직사각형의 크기를 구해야한다.
구간을 나누기 위해서는
현재 어디까지 탐색을 했고,
왼쪽이나 오른쪽에 또 다른 구간이 있나 확인해야하는데,
인덱스를 저장하면 가능하다!
2. 왜 가장 작은 높이?
높이가 [1, 2, 3, 4, 5]인 구간을 가정해보자.
즉, 길이가 5인 구간이다.
이 때의 가장 큰 직사각형의 넓이는 5이다.
[2, 3]인 구간일 때는
이 때의 가장 큰 직사각형의 넓이는 4이다.
가장 작은 높이가 영향을 주는 것을 알 수 있다.
<소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <iostream>
#include <vector>
#include <cmath>
typedef long long ll;
using namespace std;
vector<int> segment;
int arr[100000];
int n;
// 인덱스를 저장한다.
void make_segment(int node, int start, int end)
{
if (start == end)
{
segment[node] = start;
return;
}
int mid = start + (end - start) / 2;
make_segment(node * 2, start, mid);
make_segment(node * 2 + 1, mid + 1, end);
// 높이의 최소값의 인덱스를 저장
if (arr[segment[node * 2]] <= arr[segment[node * 2 + 1]])
segment[node] = segment[node * 2];
else
segment[node] = segment[node * 2 + 1];
}
// 높이 최소 인덱스 쿼리
int find_idx(int node, int start, int end, int left, int right)
{
// 탐색 범위가 쿼리 범위 밖
if (right < start || left > end)
return -1;
if (left <= start && end <= right)
return segment[node];
int mid = start + (end - start) / 2;
int left_idx = find_idx(node * 2, start, mid, left, right);
int right_idx = find_idx(node * 2 + 1, mid + 1, end, left, right);
if (left_idx == -1)
return right_idx;
if (right_idx == -1)
return left_idx;
if (arr[left_idx] <= arr[right_idx])
return left_idx;
return right_idx;
}
ll find_area(int start, int end)
{
int min_idx = find_idx(1, 0, n - 1, start, end);
ll result = (ll)(end - start + 1) * (ll)arr[min_idx];
// 높이가 최소인 인덱스를 기준으로 왼쪽, 오른쪽 나눈다.
if (start <= min_idx - 1)
{
ll left_result = find_area(start, min_idx - 1);
result = max(result, left_result);
}
if (min_idx + 1 <= end)
{
ll right_result = find_area(min_idx + 1, end);
result = max(result, right_result);
}
return result;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
while (1)
{
segment.clear();
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
cin >> arr[i];
int h = (int)ceil(log2(n));
int tree_size = (1 << (h + 1));
segment.resize(tree_size);
make_segment(1, 0, n - 1);
ll ans = find_area(0, n - 1);
cout << ans << '\n';
}
return 0;
}
|
cs |