parent link: algorithms

---

종만북::FENCE 포스팅의 사본

상태: Not started

브루트포스로 문제를 풀기엔 테스트 케이스의 크기가 너무 크다. 모든 left, right에 대해
사각형의 크기를 구한 뒤 최댓값을 구하기만 하면 된다.

## 케이스를 쪼개라, 각개격파

(사실 이런 아이디어가 있다는 사실, 그러니까 중간인덱스를 걸친 사각형의 크기를 구한다는 발상이 나에겐 처음이고 마치 전체를 순회하는 것처럼 보이지만 시간 복잡도가 O(N)밖에 되지 않는다는 점도 충격이었다.)
case [I]: 중간인덱스 (이후 pivot) 보다 작은 인덱스 판자들 중에서 가장 큰 너비
case [II]: pivot보다 큰 인덱스 판자들 중에서 가장 큰 너비
case [III]: pivot을 걸친 인덱스 판자들 중에서 가장 큰 너비

case[I],[II]의 시간복잡도는 병합정렬에서 보았듯이 O(lgN)의 시간이 걸린다.
case[III]의 경우는 pivot을 걸친 사각형을 찾는 작업밖에 없으니 O(N)이 걸린다.
각각의 이터레이션 마다 case[III]를 작업하니 O(NlgN)

// case [I]: [begin, pivot) 구간의 판자들 중에서 가장 큰 너비
// case [II]:[pivot, end) 구간의 판자들 중에서 가장 큰 너비
int pivot = (int)((begin+end) / 2);
int ret = max(  solve(begin, pivot),    solve(pivot, end)  );

// case [III]: pivot 인덱스를 포함하는 최대너비의 직사각형을 구한다.
    ret = max(ret,
        [&]() -> int
        {
            int lo=pivot, hi=pivot;
            int height=fence[pivot];
            int ret=height;
            while( begin<lo || hi<end-1 )
            {
                if (lo==begin && hi<end-1)
                {
                    hi++;
                    height=min( height, fence[hi] );
                }
                else if (hi==end-1 && begin<lo)
                {
                    lo--;
                    height=min( height, fence[lo] );
                }
                else if (fence[lo-1] < fence[hi+1])
                {
                    hi++;
                    height=min( height, fence[hi] );
                }
                else
                {
                    lo--;
                    height=min( height, fence[lo] );
                }
                ret=max( ret, height*(hi-lo+1) );
            }
            return ret;
        }()
    );

논리식에서 시간을 조금 까먹었다. 내가 end를 포함하지 않는 배열을 사용한다는 것을 새까맣게 까먹고 자꾸 인덱스를 초과하여 프로그램을 짠 것이었다. 잘 모르겠으면 위처럼 if문을 여러번 사용하고 같은 코드를 여러번 사용한 다음에 하나씩 합쳐나가는 방법도 좋겠다.