[종만북] - fence(분할정복)

문제

접근방법

분할정복.

3개로 분할하는데,

하나는 왼쪽, 하나는 중간, 하나는 오른쪽.

 

주목해봐야할 부분은 중간에 걸친 사각형의 최댓값을 계산하는 부분이다.

for loop이 돌 때마다 더 높은 막대를 선택하고,

ret와 비교해서 더 큰 값을 고른다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define FASTERINIT ios_base::sync_with_stdio(false); cin_tie(0); cout_tie(0);
#define INF 987654321

int C, n;
vector<int> 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));

    //부분문제3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
    int lo = mid, hi = mid+1;
    int height = min(h[lo], h[hi]);
    //[mid, mid+1]만 포함하는 너비 2인 사각형을 고려한다.
    ret = max(ret, height * 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, height * (hi - lo + 1));
    }
    return ret;
}

int main() {

    cin >> C;
    while(C--) {
        cin >> n;
        h = vector<int>(n);
        FOR(i, n) cin >> h[i];
        cout << solve(0, n-1) << endl;
    }

    return 0;
}

개선할 점

..