[알고스팟] 울타리 잘라내기 - 분할 정복, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

울타리 잘라내기(링크)

접근 방법

부분적으로 잘라낸 울타리의 최대 크기를 구하기 위해 분할 정복 기법을 사용했다. 주어진 울타리를 나무 판자 한개가 될 때까지 절반으로 분할하면 한개가 된 나무 판자 (한 조각의 부분 문제) 의 크기가 가장 작은 부분 문제의 답(기저 사례)이 된다.  

 

울타리는 항상 절반으로 나누어져 왼쪽, 오른쪽 부분 울타리의 최대 크기를 가져오는데, 울타리를 합쳤을 때 왼쪽과 오른쪽 울타리에 걸쳐서 잘라낼 수 있는 것의 크기도 고려해 더 큰 울타리를 만들 수 있는지 확인해야 한다. 따라서 합치는 과정에서 중간 두개의 나무 판자로부터 양쪽으로 확장해 나가며 현재 왼쪽, 오른쪽 울타리 중 큰 울타리보다 더 큰 울타리를 만들 수 있는지 확인한다. 

디버그 기록

양쪽 끝의 나무 판자까지 확장된 상태에서 woods[left - 1] < woods[right + 1] 검사를 하면 범위를 넘어가는 접근이 된다. vector container의 요소 접근을 [ ]로 했을 때 오류를 일으키지 않는다는 점과 마지막 범위를 초과하는 접근에 대해 0을 반환한다는 것이 우연히 예제를 통과하도록 했는데, [ ]를 .at() 멤버 함수로 바꾼 후 당연히 작동하지 않았다.

 

따라서 c++의 조건문에서 short-circuit evaluation을 이용해 마지막 나무 판자에서는 더 이상 다음번 판자의 크기 비교를 하지 않도록 했다. 

 

 → if (right < hi && (left == lo || woods.at(left - 1) < woods.at(right + 1)))  

 → 오른쪽 끝에 도달했다면 right < hi 가 거짓으로 이후의 조건을 확인하지 않는다.

 → 왼쪽 끝에 도달했다면 left == lo이므로 이후의 조건을 확인하지 않는다.

시간 복잡도

문제를 항상 절반으로 나누므로  O(lgn). 재귀 함수에서는 너비가 n인 사각형을 너비 2인 사각형에서 좌우로 확장하며 모두 검사하므로 O(n) 이다. 따라서 아래의 코드는 O(nlgn) 의 시간 복잡도를 가진다.

 

#include <iostream>
#include <vector>
using namespace std;

int fence(vector<int> woods, int lo, int hi) {
    // Base case: If only one wood left, return the size of it.
    if (hi == lo) return woods.at(lo);

    // Choose the bigger one between the left and right woods.
    int mid = (lo + hi) / 2;
    int leftWood = fence(woods, lo, mid);
    int rightWood = fence(woods, mid + 1, hi);

    int ret = max(leftWood, rightWood);

    int left = mid, right = mid + 1;
    int length = 2, height = min(woods.at(left), woods.at(right));
    ret = max(ret, length * height);

    while (lo < left || right < hi) {
        // Expand to the right side.
        if (right < hi && (left == lo || woods.at(left - 1) < woods.at(right + 1))) {
            right += 1;
            // If the new wood's height is lower than the current fence,
            // fence expansion will be lower than the current height.
            if (woods.at(right) < height) height = woods.at(right);
        // Expand to the left side.
        } else { 
            left -= 1;
            if (woods.at(left) < height) height = woods.at(left);
        }
        length += 1;
        ret = max(ret, length * height);
    }

    return ret;
}

int main() {
    int C; cin >> C;
    int woodNum;
    vector<int> answers, woods;

    while (C-- > 0) {
        cin >> woodNum;
        woods = vector<int>(woodNum);
        for (auto& e: woods) cin >> e;
        
        answers.push_back(fence(woods, 0, woodNum - 1));
    }

    for (const auto& e: answers) cout << e << endl;
    return 0;
}