[알고스팟/C,C++] FENCE: 울타리 잘라내기

www.algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

도무지 풀이가 떠오르지 않아 알고리즘 문제 해결 전략의 코드를 참고하여 풀었습니다 ㅜㅜ

 

반으로 잘라도 옆의 사각형과 연결을 시켜야 하는데 이 부분에서 애를 많이 먹었는데요.

 

중간을 기점으로 분할한 왼쪽과 오른쪽 중 큰 사각형을 받아오고

 

그 사각형을 기준으로 현재 검색할 구간의 끝까지 사각형을 합쳐 더 큰 사각형을 계속 반환합니다.

 

int dv(int left, int right)
{
    if (left == right) return fence[left];
    int mid = (left + right) / 2;
    int ret = max(dv(left, mid), dv(mid + 1, right));
    
    int lp = mid;
    int rp = mid;
    int height = fence[mid];

    while (left < lp || rp < right) {
        if (left < lp && (rp == right || fence[lp - 1] > fence[rp + 1])) {
            --lp;
            height = min(height, fence[lp]);
        }
        else {
            ++rp;
            height = min(height, fence[rp]);
        }
        ret = max(ret, height * (rp - lp + 1));
    }
    return ret;
}

 

예제 입력을 예로 들어 그림으로 보면 이렇습니다.

 

값은 7 1 5 9 6 7 3 입니다.

 

 

각 분할 단계를 순서대로 A → B → C 라고 할 때, 최초 기저 사례에 도달하는 분할 단계는 C입니다.

 

C를 기준으로 좌우는 파라미터가 (0, 0), (1, 1)으로 들어간 상태이며, left == right이기 때문에..

 

0번 블록과 1번 블록을 바로 반환합니다.

 

 

이제 B를 기준으로 좌우는 파라미터가 (0, 1), (2, 3)으로 들어간 상태입니다.

 

이때, 파라미터가 (0, 1)로 들어간 함수 호출에서 3번째 구문으로 인해 ret에 0번 블록이 담긴 상태입니다.

 

left와 right가 같지 않기 때문에, mid에서부터 현재 구간(0~1) 중에 높이가 가장 높은 쪽으로 사각형을 더해 갑니다.

 

mid가 0이므로 더 이상 왼쪽으로는 탐색이 불가능합니다.

 

오른쪽으로 탐색이 가능한데 0번 블록과 1번 블록에서 찾을 수 있는 가장 큰 직사각형은 넓이가 2입니다.

 

0번 블록은 넓이가 7이기 때문에, ret 값은 바뀌지 않죠.

 

탐색이 모두 끝났으므로 0~1구간을 탐색한 함수에서는 7을 반환합니다.

 

 

2~3구간을 탐색한 함수에서는 10을 반환하겠죠.

 

3번 블록은 넓이가 9이기 때문에, 2번 블록과 3번 블록에서 찾은 넓이 10이 반환되는 것입니다.

 

이제 0~3구간을 탐색하게 됩니다.

 

이때 반복되는 패턴이 있는데 분할된 선을 기준으로 왼쪽에서 가장 큰 사각형, 오른쪽에서 가장 큰 사각형

 

그리고 중간에서부터 탐색한 사각형을 비교하여 제일 큰 값을 반환한다는 것입니다.

 

 

즉 0~3구간에서는 왼쪽에서 가장 큰 사각형(1번), 오른쪽에서 가장 큰 사각형(2번)

 

중간에서 좌우로 탐색하며 찾은 사각형들(3번) 중 가장 큰 값을 계속해서 찾습니다.

 

#include<iostream>

using namespace std;

const int MAX = 20000;

int fence[MAX];

int dv(int left, int right)
{
    if (left == right) return fence[left];
    int mid = (left + right) / 2;
    int ret = max(dv(left, mid), dv(mid + 1, right));
    
    int lp = mid;
    int rp = mid;
    int height = fence[mid];

    while (left < lp || rp < right) {
        if (left < lp && (rp == right || fence[lp - 1] > fence[rp + 1])) {
            --lp;
            height = min(height, fence[lp]);
        }
        else {
            ++rp;
            height = min(height, fence[rp]);
        }
        ret = max(ret, height * (rp - lp + 1));
    }
    return ret;
}

int main(void)
{
    int c; cin >> c;

    for (int i = 0; i < c; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> fence[j];
        }
        cout << dv(0, n - 1) << "\n";
    }

    return 0;
}