[알고스팟] 울타리 잘라내기

문제 링크

울타리 잘라내기

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • FENCE
  • 3000ms
  • 131072kb
  • 9487
  • 2890 (30%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 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

어떻게 접근할까?

 

 해당 문제는 분할 정복 문제로 풀 수 있습니다.

 우선, 큰 영역을 가운데로 왼쪽과 오른쪽의 작은 공간으로 나눈다고 생각합시다.

 그러면 해당 문제는 4 단계를 거쳐서 해결 방법을 찾을 수 있습니다.

 1. 영역의 왼쪽 부분에서 최대 사각형의 넓이를 구합니다.

 2. 영역의 오른쪽 부분에서 최대 사각형 넓이를 구합니다.

 3. 영역의 양 쪽에 걸친 부분에서 최대 사각형의 넓이를 구합니다.

 4. 위의 3가지 넓이 중에서 최댓값을 선택합니다.

기저 사례는 더 이상 쪼개질 수 없는 상황, 즉 울타리 1개만이 남게 됐을 때가 됩니다.

이 때, 울타리 하나 크기의 넓이를 반환합니다.

그렇다면 이제, 영역의 양 쪽에 걸친 부분에서 최대 사각형의 넓이를 구하는 것이 핵심이라고 할 수 있습니다.

포인트는 양 쪽에 모두 걸쳐있다는 것입니다!

따라서, 가운데 부분의 사각형은 무조건 왼쪽 영역에서 가장 오른쪽 울타리와 오른쪽 영역에서 가장 왼쪽편에 있는 울타리 2개를 포함해야 합니다.

이 포함된 울타리의 넓이는 현재 포함된 울타리 중에서 가장 낮은 높이를 너비만큼 곱한 값이 될 것입니다. 

현재는 포함된 울타리가 2개이므로 2개 중에 가장 낮을 울타리의 높이에 2를 곱하면 됩니다.

이제 여기서 포함된 울타리 양 옆으로 가장 큰 울타리를 하나씩 선택합니다. 그리고 높이가 가장 낮은 울타리 만큼 넓이를 더해나가면서

최대의 넓이를 가지는 경우를 저장하면 바로 가운데 부분에서 가장 넓은 높이를 가지는 사각형을 구할 수 있습니다!

시간 복잡도를 생각해봅시다.

우선 너비를 절반 씩 쪼개므로 쪼개지는 단계는이 될 것입니다.

그리고 가운데 부분의 넓이를 구하기 위해 left에서 right까지 각 단계마다 N번의 연산이 수행됩니다.

따라서 전체적인 시간 복잡도는  이 됩니다!

이를 이용하여 분할 정복을 통해서 문제를 풀 수 있습니다!

코드

//FENCE : 울타리 잘라내기
//알고스팟
//https://algospot.com/judge/problem/read/FENCE
 
#pragma once
#include<cstdio>
 
int h[20000];
 
int getMax(int i1, int i2, int i3)
{
    if (i1 > i2)
    {
        return i1 > i3 ? i1 : i3;
    }
 
    else
    {
        return i2 > i3 ? i2 : i3;
    }
}
 
int getMin(int i1, int i2)
{
    return i1 < i2 ? i1 : i2;
}
 
int getMaxArea(int left, int right)
{
    if (left + 1 == right)
    {
        return h[left];
    }
 
    int half = (left + right) / 2;
    int s = 0, area = 0, l = half - 1 , r = half, blockNum = 0;
    int minH = getMin(h[l], h[r]);
 
    while (l >= left && r < right)
    {
        blockNum++;
 
        if (h[l] > h[r])
        {
            minH = getMin(minH, h[l--]);
            s = blockNum * minH;
            area = area > s ? area : s;
        }
        else
        {
            minH = getMin(minH, h[r++]);
            s = blockNum * minH;
            area = area > s ? area : s;
        }
    }
    
    while (l >= left)
    {
        blockNum++;
        minH = getMin(minH, h[l--]);
        s = blockNum * minH;
        area = area > s ? area : s;
    }
 
    while (r < right)
    {
        blockNum++;
        minH = getMin(minH, h[r++]);
        s = blockNum * minH;
        area = area > s ? area : s;
    }
 
    return getMax(getMaxArea(left, half), getMaxArea(half, right), area);
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        int n;
        scanf("%d\n", &n);
 
        for (int i = 0; i < n; i++)
        {
            scanf("%d \n", h + i);
        }
 
        printf("%d\n", getMaxArea(0, n));
    }
    return 0;
 
}

여담

 스위핑과 스택을 이용하면 선형 시간에 해당 문제를 풀 수 있다고 합니다. 나중에 이쪽을 다시 다루게 된다면 글을 수정해서 또다른 풀이를 올리겠습니다.