문제
풀이
Reference를 참조하였다. O(N^2)으로 문제를 풀었지만, 시간초과로 인해 실패하였다. 시간초과를 면하기 위한 알고리즘은 분할정복 + 세그먼트트리를 이용한 알고리즘이다.
0 ~ N-1구간에서 높이의 최솟값인 index를 찾고 그 index를 통해 넓이를 구해 나가 최대 넓이를 찾는 문제이다. 세그먼트 트리를 진행하여, 각 세그먼트 트리 노드에 높이의 최솟값을 index에 저장해놓는다.
solve에서는 특정 구간이 해당하는 곳을 찾아 index를 반환하는 query함수를 거쳐 넓이를 구하고 해당 구간 높이의 최솟값의 index의 왼쪽 오른쪽 구간으로 나누어 계속해서 재귀호출하여 max값들을 계속 갱신한다.
세그먼트 트리에 대해서 알게된 문제이며, 세그먼트 트리에 대해서는 Reference에 자세히 설명되어 있다.
소스 코드
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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 2000000000 // 20억
long long n;
long long seg[1000001];
long long x, ans;
long long h[100001];
int init(int node, int s, int e)
{
if (s == e) return seg[node] = s; // start 와 end 의 위치가 일치하면 인덱스 s 값을 넣어준다.
int mid = (s + e) / 2;
int left_index = init(2 * node, s, mid);
int right_index = init(2 * node + 1, mid + 1, e);
return seg[node] =
h[left_index] < h[right_index] ? left_index : right_index;
}
int query(int node, int s, int e, int l, int r)
{
if (e < l || r < s) return INF; // 찾아야하는 구간과 노드구간이 겹치지 않을 때
if (l <= s && e <= r) return seg[node]; // 찾아야하는 구간내에 노드구간이 포함될 때
int mid = (s + e) / 2;
int left_index = query(2 * node, s, mid, l, r);
int right_index = query(2 * node + 1, mid + 1, e, l, r);
// 찾아야하는 구간이 노드구간에 포함되거나, 부분적으로 겹치는 경우
if (left_index == INF) return right_index; // 에러방지
else if (right_index == INF) return left_index; // 에러방지
else return h[left_index] < h[right_index] ? left_index : right_index;
}
void solve(long long left, long long right)
{
if (left > right) return;
// 구간내의 최소값과 해당 인덱스 찾기
long long index = query(1, 0, n - 1, left, right); // 구간 내의 최소값 찾기
ans = max(ans, h[index] * (right - left + 1));
solve(left, index - 1);
solve(index + 1, right);
}
int main()
{
while (1)
{
ans = 0;
cin >> n;
if (n == 0) break;
for (int i = 0; i < n; i++)
{
cin >> h[i];
}
init(1, 0, n - 1); // 세그먼트 트리 만들기
solve(0, n - 1);
cout << ans << endl;
}
}
