FENCE

문제 링크

FENCE

문제 풀이

직사각형의 넓이의 최대값을 구하는 문제이다. 울타리를 반으로 나누어 왼쪽 부분에서의 최대값과 오른쪽 부분에서의 최대값을 재귀 호출로 구한다. 그리고 양쪽 부분에 둘다 걸린 직사각형의 넓이를 for문을 돌려구한 뒤, 세 값들을 비교하여 최대값을 구한다. 양쪽 부분에 걸린 직사각형의 넓이를 구하기 위해서 일단 중간에 위치한 mid와 mid+1 기둥을 포함하고, 하나씩 추가해간다. 오른쪽과 왼쪽 기둥 중 두 기둥의 높이를 비교하여 더 높은 곳을 먼저 추가해나간다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int TC, N;
vector<int> fence;
int solve(int left, int right) {
    if (left == right) return fence[left];

    int mid = (left + right) / 2;

    int ret = max(ret, solve(left, mid));
    ret = max(ret, solve(mid + 1, right));

    int minFence = min(fence[mid], fence[mid + 1]);
    int area = minFence * 2;
    int l = mid, r = mid + 1;

    while (left < l || r < right) {
        if (left < l && (r == right || fence[l - 1] > fence[r + 1])) {
            --l;
            minFence = min(minFence, fence[l]);
        }
        else {
            ++r;
            minFence = min(minFence, fence[r]);
        }
        area = max(area, minFence * (r - l + 1));
    }
    ret = max(ret, area);
    return ret;
}

int main() {
    cin >> TC;
        while (TC--) {
        cin >> N;
        fence.clear();
        for (int i = 0; i < N; ++i) {
            int temp;
            cin >> temp;
            fence.push_back(temp);
        }
        cout << solve(0, N - 1) << "\n";
    }
    return 0;
}