[분할 정복] FENCE

[1. 문제 재정의 및 추상화]

1. 너비가 같은 N 개의 나무 판자에서 잘라낼 수 있는 많은 직사각형 중 가장 큰 직사각형의 넓이
2. 단, 비스듬히 잘라 낼 수 없다.
3. N 은 최대 20000 까지 주어짐
4. TestCase 는 최대 50 까지 주어짐

 

[2. 해결 계획]

1. 완전 탐색에서 시작
   left = 0 ~ right = N 까지 범위에서 최대 넓이를 찾고
   left = 1 ~ right = N 까지 범위에서 최대 넓이를 찾고,
   ...
2. 분할 정복으로 계산 한다면,
   A) 가장 넓은 직사각형이 중앙에서 왼쪽에 존재하는 경우
   B) 가장 넓은 직사각형이 중앙에서 오른쪽에 존재하는 경우
   C) 가장 넓은 직사각형이 왼쪽과 오른쪽에 걸쳐있는 경우
   Case C 의 경우, 최초에는 중앙에 두개의 판자를 모두 덮을 수 있게 둘 중 최소를 높이로 선택해야 함.
   이 후, 왼쪽 또는 오른쪽으로 움직일 때는 한 쪽 방향으로만 움직이므로 둘 중 최대를 높이로 선택하고, 기존 높이와 비교하여 모든 판자를 덮을 수 있게 최소를 높이로 선택하고, 직사각형 넓이 계산 후 최대인 경우 업데이트 해야함 

 

[3. 계획 검증]

1. 완전 탐색은 O(N^2) 이므로 최대 입력인 경우 200억 (50*20000*20000) 이므로 주어진 시간 내 해결 불가
2. 분할 정복은 Case A, B 는 O(logN) 개 발생하고 상수 시간 내 해결 가능, Case C 의 경우 최대 n 번의 반복문이 발생하므로, O(NlogN) 으로 해결 가능

[4. 완전 탐색 풀이]

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

int bruteforce(const std::vector<int>& h)
{
    int ret = 0;
    const std::size_t len = h.size();
    for (auto left = 0; left < len; left++)
    {
        int minHeight = h[left];
        for (auto right = left; right < len; right++)
        {
            // 넓이는 밑변 (right - left + 1) 과
            // 높이에 의존한다.
            // 높이는 범위 [left, right] 내 모든 Fence 에서 얻을 수 있어야하므로
            // 하한 값을 선택해야 한다.
            minHeight = std::min(minHeight, h[right]);
            ret = std::max(ret, (right - left + 1) * minHeight);
        }
    }
    return ret;
}

int main()
{
    int C, N, t;
    scanf("%d", &C);
    
    for (int c = 0; c < C; c++)
    {
        scanf("%d", &N);
        std::vector<int> h;
        h.reserve(N);
        for (int n = 0; n < N; n++)
        {
            scanf("%d", &t);
            h.push_back(t);
        }

        printf("%d\n", bruteforce(h));
    }
}

 

[5. 분할 정복 풀이]

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

int solve(const std::vector<int>& h, const int left, const int right)
{
    // 기저사례, 밑변이 1 인 경우
    if (left == right) {
        return h[left];
    }

    // Divide => case1, case2
    const int mid = (left + right) / 2;
    // Left / Right
    int ret = std::max(solve(h, left, mid), solve(h, mid+1, right));
    
    // 왼쪽과 오른쪽에 걸쳐있는 경우
    int lo = mid;
    int hi = mid+1;
    int height = std::min(h[lo], h[hi]);
    // 중심에서 왼쪽 또는 오른쪽으로 이동 할 수 있다면,
    while (left < lo || hi < right)
    {
        // 오른쪽으로 이동할 수 있고,
        // 왼쪽으로는 더 이상 갈 수 없거나 
        // 오른쪽 Fence의 높이가 더 큰 경우
        // 오른쪽 높이와 기존 높이 중 모든 Fence 를 덮을 수 있게
        // 하한 값을 선택
        if (hi < right && (left == lo || h[lo-1] < h[hi+1]))
        {
            hi++;
            height = std::min(height, h[hi]);
        }
        else 
        {
            // 오른쪽으로 갈 수 없거나(반복문 조건 상 왼쪽은 갈 수 있음)
            // 둘다 이동 할 수 있는데, 왼쪽 Fence의 높이가 더 큰 경우
            lo--;
            height = std::min(height, h[lo]);
        }
        // 모든 Fence 를 덮을 수 있는 높이
        // 와 밑면을 곱하여 새로운 넓이를 구하고
        // 최대값을 찾는다.
        ret = std::max(ret, (hi-lo+1)*height);
    }

    return ret;
}

int main()
{
    int C, N, t;
    scanf("%d", &C);
    
    for (int c = 0; c < C; c++)
    {
        scanf("%d", &N);
        std::vector<int> h;
        h.reserve(N);
        for (int n = 0; n < N; n++)
        {
            scanf("%d", &t);
            h.push_back(t);
        }

        printf("%d\n", solve(h, 0, N-1));
    }
}