[FENCE] 울타리 잘라내기

• 입력: 테스트케이스 C(C≤50), 판자의 수(1≤N≤20,000), hi(0≤hi≤10,000)
• 출력: 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기
• 알고리즘: 세그먼트 트리, 분할정복
• 소스코드
#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번 문제와 입력만 다를 뿐 완전히 같은 문제로, 전에 풀었던 코드를 전혀 보지 않고 풀려고 풀었다. 단점이자 장점이 단기기억력이 좋다는건데 안 보고 구현했음에도 불구하고 굉장히 유사한 코드로 구현이 됐다.