울타리 잘라내기
알고스팟 문제: https://algospot.com/judge/problem/read/FENCE
algospot.com :: FENCE
울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대
algospot.com
입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.
출력
각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.
(종만북 참고) 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 20000;
int N;
vector h;
int solve(int left, int right)
{
if (left == right) return h[left];
int mid = (left + right) / 2;
int ret = max(solve(left, mid), solve(mid + 1, right)); // 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다
int lo = mid, hi = mid + 1;
int height = max(h[lo], h[hi]);
ret = max(ret, height * 2); // [mid, mid+1]만 포함하는 너비 2 인 사각형을 고려한다
while (left < lo || hi < right) // 사각형이 경계사이에 있을경우, 입력 전체를 덮을 때까지 확장해 나간다
{
if (hi < right && (lo == left || h[lo - 1] < h[hi + 1]))
{
hi++;
height = min(height, h[hi]);
}
else
{
lo--;
height = min(height, h[lo]);
}
ret = max(ret, (hi - lo + 1) * height);
}
return ret;
}
int main()
{
int C;
cin >> C;
while (C--)
{
h.clear();
cin >> N;
for (int i = 0; i < N; ++i)
{
int height;
cin >> height;
h.push_back(height);
}
int answer;
answer = solve(0, N - 1);
cout << answer << endl;
}
return 0;
}
