SQL로 이 문제를 분할 정복법을 활용하여 해결하는 것은 다음과 같다.

 

with base as (

            select  1 no , 7 h from    dual

union all   select  2 no , 1 h from    dual

union all   select  3 no , 5 h from    dual

union all   select  4 no , 9 h from    dual

union all   select  5 no , 6 h from    dual

union all   select  6 no , 7 h from    dual

union all   select  7 no , 3 h from    dual

)

, base_recur ( min_no, max_no, center_no ,lvl ) as

(

    select

        min(no) min_no

        ,max(no) max_no

        ,trunc((max(no) + 1) / 2) center_no

        , 1

    from    base a

    union all

    select

        case when b.lvl = 1 then a.min_no else a.center_no + 1 end min_no

        ,case when b.lvl = 1 then a.center_no else a.max_no end max_no

        ,trunc(((case when b.lvl = 1 then a.min_no else a.center_no + 1 end) + (case when b.lvl = 1 then a.center_no else a.max_no end)) / 2 ) center_no

        ,a.lvl + 1

    from    base_recur a

            , (

                select

                    level lvl

                from    dual

                connect by level < 3

            ) b

    where   a.min_no < a.max_no

    and     a.lvl < 10

)

, calc_recur ( min_no, max_no, center_no, lvl, calc_min_no, calc_max_no,cur_h,area ,calc_seq) as

(

    select

        a.min_no

        ,a.max_no

        ,a.center_no

        ,a.lvl

        ,a.center_no calc_min_no

        ,a.center_no calc_max_no

        ,b.h

        ,b.h

        , 1

    from    base_recur a

            , base b

    where   b.no = a.center_no

    union all

    select

        a.min_no

        ,a.max_no

        ,a.center_no

        ,a.lvl

        ,case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end calc_min_no

        ,case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end calc_max_no

        ,least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h)

        ,least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h) *

            (

                case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end

                - case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end

            + 1)

        ,calc_seq + 1

    from    calc_recur a

            , base b1

            , base b2

    where   b1.no (+) = a.calc_min_no - 1

    and     b2.no (+) = a.calc_max_no + 1

    and     not (a.calc_min_no - 1 < a.min_no and a.calc_max_no + 1 > a.max_no )

    and     not (

                case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end = a.calc_min_no

            and case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end = a.calc_max_no

            )

    and     least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h) > 0

)

select

    max(a.area) area

    ,count(*) cnt

from    calc_recur a

/

 

 

sql이 엄청 복잡해진 것은 내가 실력이 부족해서이고

sql로 재귀호출을 할 수는 없으니(왜냐면 함수가 아니니까)

재귀호출에 의해서 문제가 분할 되는 것을 recursive-with 절을 사용하여 만들어 낸 다음

만들어진 분할된 부분 문제를 해결하고

이를 다시 병합하면 되는 것이다.

 

여기서 핵심 아이디어는 recursive-with 절을 사용한 문제의 재귀적 분할이며

위의 경우는 base_recur 부분이 되겠다.

base_recur 부분에서 원 문제를 연속적으로 두 부분의 부분문제로 만들어 낸다.

base_recur 부분만 select 해보면 그 결과는 다음과 같은데.

 

 

MIN_NO	MAX_NO	CENTER_NO	LVL
1	7	4	1
1	4	2	2
5	7	6	2
1	2	1	3
3	4	3	3
5	6	5	3
7	7	7	3
1	1	1	4
2	2	2	4
3	3	3	4
4	4	4	4
5	5	5	4
6	6	6	4

 

이 목록은 재귀호출을 통해서 문제를 분할할 경우의 목록과 일치하게 된다.

 

그런 다음 부분문제를 해결하는 것은 

책 프로그래밍대회에서 배우는 알고리즘 문제해결전략 1권의 195 페이지를 참조하면 된다.