[FENCE] 울타리 잘라내기

• 입력: 테스트케이스 C(C≤50), 판자의 수(1≤N≤20,000), hi(0≤hi≤10,000)
• 출력: 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기
• 알고리즘: 세그먼트 트리, 분할정복
• 소스코드
?

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

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <cmath> using namespace std;   #define MAX 20 * 1000 + 1   int N; vector<int> wood, tree; void init(int, int, int); int retIndex(int, int, int, int, int); int maxS(int, int); int max(int a, int b) { return (a > b ? a : b); }   int main() {     int C;     scanf("%d", &C);     while (C--) {         scanf("%d", &N);         wood = vector<int>(N, MAX);         for (int i = 0; i < N; i++)             scanf("%d", &wood[i]);           int h = (int)ceil(log2(N));         int tree_size = (1 << (h + 1));           tree = vector<int>(tree_size);         init(1, 0, N - 1);         printf("%d\n", maxS(0, N - 1));     }     return 0; }   void init(int node, int start, int end) {     if (start == end) tree[node] = start;     else {         init(node * 2, start, (start + end) / 2);         init(node * 2 + 1, (start + end) / 2 + 1, end);         tree[node] = (wood[tree[node * 2]] <= wood[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1]);     } }   int retIndex(int node, int left, int right, int start, int end) {     if (end < left || start > right) return -1;     if (left <= start && right >= end) return tree[node];       int l = retIndex(node * 2, left, right, start, (start + end) / 2);     int r = retIndex(node * 2 + 1, left, right, (start + end) / 2 + 1, end);     if (l == -1) return r;     if (r == -1) return l;     return (wood[l] <= wood[r] ? l : r); }   int maxS(int left, int right) {     int index = retIndex(1, left, right, 0, N - 1);     int max_S = (right - left + 1)*wood[index];     if (left <= index - 1)         max_S = max(max_S, maxS(left, index - 1));     if (right >= index + 1)         max_S = max(max_S, maxS(index + 1, right));       return max_S; }

tree에 각 구간의 가장 낮은 높이를 가지는 인덱스를 저장한 뒤, 최대 직사각형의 크기를 구한다. 크기를 구할 때 각 구간의 가장 낮은 높이의 인덱스를 받고, 해당 인덱스를 제외하고서 양 구간의 직사각형의 크기를 재귀로 구한다.

• 참고: https://algospot.com/judge/problem/read/FENCE
• Baekjoon에서 6549번 문제와 입력만 다를 뿐 완전히 같은 문제로, 전에 풀었던 코드를 전혀 보지 않고 풀려고 풀었다. 단점이자 장점이 단기기억력이 좋다는건데 안 보고 구현했음에도 불구하고 굉장히 유사한 코드로 구현이 됐다.