7.4 울타리 잘라내기

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단, 직사각형을 비스듬히 잘라낼 수는 없습니다.
판자의 너비는 모두 1이라고 가정합니다.

시간 및 메모리 제한

프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

입력

첫 줄에 테스트 케이스의 개수 C(C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N(1<=N<=20000)가 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 자연수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

예제 입력

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

예제 출력

20
16
8

무식하게 풀기

    public static int bruteForce(int[] h) {
        int ret = 0;
        int N = h.length;
        // 가능한 모든 left, right 조합을 순회한다.
        for(int left = 0; left < N; ++left) {
            int minHeight = h[left];
            for (int right = 0 ; right < N ; ++right) {
                minHeight = Math.min(minHeight, h[right]);
                ret = Math.max(ret, (right - left + 1) * minHeight);
            }
        }
        return ret;
    }

분할 정복으로 풀기

    static int[] h;
    //h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환
    public static int solve(int left, int right) {
        // 기저 사례 : 판자가 하나밖에 없는 경우
        if(left==right) return h[left];
        // [left, mid], [mid+1, right]의 두 구간으로 문제를 분할한다.
        int mid = (left + right) / 2;
        // 분할한 문제를 각개격파
        int ret = Math.max(solve(left, mid), solve(mid+1, right));
        // 부분 문제 3 : 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
        int lo = mid, hi = mid+1;
        int height = Math.min(h[lo], h[hi]);
        // [mid, mid+1]만 포함하는 너비 2인 사각형을 고려한다.
        ret = Math.max(ret, height*2);
        // 사각형이 입력 전체를 덮을 때까지 확장해 나간다.
        while(left < lo || hi < right) {
            // 항상 높이가 더 높은 쪽으로 확장한다.
            if(hi < right && (lo == left || h[lo-1] < h[hi+1])) {
                ++hi;
                height = Math.min(height, h[hi]);
            }
            else {
                --lo;
                height = Math.min(height, h[lo]);
            }
            // 확장한 후 사각형의 넓이
            ret = Math.max(ret, height * (hi - lo + 1));
        }
        return ret;
    }

#책/종만북