[Java] 알고스팟 : FENCE

문제 링크

1.

분할 정복 문제

입력의 최대 크기가 20,000이므로 완전 탐색으로 풀기에는 시간 초과가 날 것.

 

2.

자세한 풀이는 책 참고 (p.196)

 

• $n$개의 판자를 절반으로 나눠 두 개의 부분 문제를 만들자.
• 최대 직사각형은 다음 세 가지 중 하나에 속할 것
• 1. 왼쪽 부분 문제에 존재
• 2. 오른쪽 부분 문제에 존재
• 3. 왼쪽과 오른쪽 부분 문제에 걸쳐서 존재
• 1번과 2번은 어렵지 않으나 3번의 경우 왼쪽, 오른쪽 부분을 높이가 높은 쪽으로 한 칸씩 확장하면서 찾자.

 

3.

import java.util.Scanner;

public class FENCE {
    static int[] h;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();

        for (int i = 0; i < c; i++) {
            int n = sc.nextInt();
            h = new int[n];
            for (int j = 0; j < n; j++) {
                h[j] = sc.nextInt();
            }
            System.out.println(solve(0, n - 1));
        }

        sc.close();
    }

    static int solve(int left, int right) {
        // 기저 사례
        if (left == right) {
            return h[left];
        }

        // 분할 정복
        int mid = (left + right) / 2;
        int ret = Math.max(solve(left, mid), solve(mid + 1, right));

        // 양쪽 부분 문제에 걸친 경우의 답
        int lo = mid, hi = mid + 1;
        int height = Math.min(h[lo], h[hi]);
        ret = Math.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 = Math.min(height, h[hi]);
            } else {
                lo--;
                height = Math.min(height, h[lo]);
            }

            ret = Math.max(ret, height * (hi - lo + 1));
        }
        return ret;
    }
}

 

 

4.

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만)

[참고] https://www.youtube.com/watch?v=Ud29HJqfFsM