[6549] 히스토그램에서 가장 큰 직사각형

• 입력: 직사각형의 수 n(1≤n≤100,000) , n개의 직사각형의 높이 hi(1≤hi≤1,000,000,000), n = 0이면 종료
• 출력: 각 테스트케이스에 대해서, 히스토그램에서 가장 큰 직사각형의 넓이
• 알고리즘: 세그먼트 트리
• 실패한 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std; #define ll long long #define MAX 1000*1000*1000 + 1 ll min(ll a, ll b) { return (a < b ? a : b); } ll max(ll a, ll b) { return (a > b ? a : b); } ll init(vector<ll>& height, vector<ll>& arr, ll node, ll start, ll end) { if (start == end) return height[node] = arr[start]; else return height[node] = min(init(height, arr, node * 2, start, (start + end) / 2), init(height, arr, node * 2 + 1, (start + end) / 2 + 1, end)); } ll retHeight(vector<ll>& tree, vector<ll>& height, ll node, ll start, ll end) { if (start == end) return tree[node] = height[node]; if (height[node] == MAX) return 0; tree[node] = (end - start + 1) * height[node]; ll max_height = tree[node]; max_height = max(max_height, retHeight(tree, height, node * 2, start, (start + end) / 2)); max_height = max(max_height, retHeight(tree, height, node * 2 + 1, (start + end) / 2 + 1, end)); return max_height; } int main() { int n; scanf("%d", &n); while (n != 0) { vector<ll> arr(n); for (int i = 0; i < n; i++) scanf("%lld", &arr[i]); ll h = (ll)ceil(log2(n)); ll tree_size = (1 << (h + 1)); vector<ll> height(tree_size, MAX); vector<ll> tree(tree_size); init(height, arr, 1, 0, n - 1); printf("%lld\n", retHeight(tree, height, 1, 0, n - 1)); scanf("%d", &n); } return 0; }

세그먼트 트리를 이용했는데, 트리에 각 구간에 대해 가장 낮은 높이를 저장해두고 높이를 따로 저장한다.

실패한 이유로는 위와 같이 하게 되면 각 구간, 1/2만큼의 사이즈에 대해서만 높이를 구하기 때문에 예를 들면 n=8일때 h3~h7까지의 넓이가 가장 크다고 해도 구할 수 없다.

즉, 가장 작은 높이를 가진 인덱스를 트리에 저장해두고 계산하는 방식으로 해야한다고 생각했다. 

• 성공한 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std; #define ll long long #define MAX 1000*1000*1000 + 1 ll max(ll a, ll b) { return (a > b ? a : b); } void init(vector<ll>& height, vector<ll>& arr, int node, int start, int end) { if (start == end) height[node] = start; else { init(height, arr, node * 2, start, (start + end) / 2); init(height, arr, node * 2 + 1, (start + end) / 2 + 1, end); height[node] = (arr[height[node * 2]] <= arr[height[node * 2 + 1]] ? height[node * 2] : height[node * 2 + 1]); } } int retHeight(vector<ll>& height, vector<ll>& arr, int node, int left, int right, int start, int end) { if (end < left || right < start ) return -1; if (left <= start && end <= right) return height[node]; // 구간 내에 있으면 int l = retHeight(height, arr, node * 2, left, right, start, (start + end) / 2), r = retHeight(height, arr, node * 2 + 1, left, right, (start + end) / 2 + 1, end); if (l == -1) return r; if (r == -1) return l; return (arr[l] <= arr[r] ? l : r); } ll maxS(vector<ll>& height, vector<ll>& arr, int left, int right, int n) { int index = retHeight(height, arr, 1, left, right, 0, n - 1); ll max_s = (ll)(right - left + 1)*arr[index]; if (left <= index - 1) max_s = max(max_s, maxS(height, arr, left, index - 1, n)); if (right >= index + 1) max_s = max(max_s, maxS(height, arr, index + 1, right, n)); return max_s; } int main() { int n; scanf("%d", &n); while (n != 0) { vector<ll> arr(n); for (int i = 0; i < n; i++) scanf("%lld", &arr[i]); ll h = (ll)ceil(log2(n)); ll tree_size = (1 << (h + 1)); vector<ll> height(tree_size, MAX); init(height, arr, 1, 0, n - 1); printf("%lld\n", maxS(height, arr, 0, n-1, n)); scanf("%d", &n); } return 0; }

인터넷을 참고하여 문제를 풀었는데 위 식은 트리에 가장 낮은 높이의 인덱스를 저장해두고, 그 중 가장 큰 넓이를 찾는 방식이다. 소스코드를 참고한 사이트는 아래 첨부해놓았다. 아직은 미숙한거 같아, 유사한 문제를 알고스팟에 풀고 다른 문제를 다시 도전해볼 예정이다.
세그먼트 트리에서는 어떤 기준으로 저장하냐와 접근하냐가 중요한 키워드인 것 같다.

• 참고: https://www.acmicpc.net/problem/6549
• 소스코드 참고: http://jason9319.tistory.com/44