[PY] 6549 : 히스토그램에서 가장 큰 직사각형

https://www.acmicpc.net/problem/6549

진짜 어려웠다. 파일럿 코를 처음부터 달고 아이디어를 생각했다.
물론 전부 다 해달라고 던진거까진 아니고, 혼잣말하면서 영역을 넓혀가듯 그냥 그런거 같네요. 아닌 것 같기도 하네요. 만 말하게 시켰다.

코 삼촌은 해달라는대로 다 해주려고 애쓰긴 한다.

그래서 메인 아이디어를 어떻게 구상했을까? 여기에 시간이 많이 필요했다.

1. 처음 주어진 내용을 전부 배열에 넣는다. 그리고 배열을 좌, 가운데, 우로 나눈다.
   • 전체 내용을 기준으로 mid를 선택하고, mid는 처음부터 제외를 한다.
     • 가운데는 일단 좌 우측에서 값이 도출 될 때까지 활용 하진 않는다.
   • 첫번째 좌측 호출 기준은 0 - mid - 1, 우측은 mid + 1 - len(histogramList) 이다.
2. 각 분야에서 똑같은 방법으로 3가지 루트로 나눈다.
3. 더 이상 나눌 수 없으면 존재하는 유일한 값이 해당 영역에서 만들 수 있는
   최대 넓이로 만들 수 있다는 뜻이니 존재하는 현 값을 반환한다. 이런 식으로 Lmax, Rmax을 만들 수 있다.
4. 그리고 해당 값들이 모두 동일 레벨에 올라왔다면 좌측 영역의 최대 넓이인 Lmax, 우측 영역의 최대 넓이인 Rmax가 있을 것이다.
5. 이 단계에서 Mmax(Middle Max)를 구해야한다. 가운데의 높이를 기준으로 좌우로 전개한다. 투 포인터 형식과 유사하다.
6. 마지막에 Lmax, Rmax, Mmax 중 max를 출력한다.

아이디어 구상을 다 끝냈지만 진짜 이런 상태였다.

뭘 어떻게 하라는건지 감이 하나도 안잡혔다.

그냥 가만히 한줄한줄 쓰니 완성이 되는것이 많이 놀랐다. 코드 자체가 완전 내 힘으로 짰다는 걸로 만족해야 할듯.

분할정복은 구간에 대한 차이만 있을 뿐 해결하는 루틴은 동일해야 한다는 핀트에서 괜찮은 소득을 얻은 문제였다.

import sys

histogram = list(map(int, sys.stdin.readline().strip().split()))
cnt = histogram[0]
histogram.remove(cnt)


# 아이템이 3개일지라도 작동할것

def calcHisto(L, R):
    if(L == R):
        return histogram[L]
    elif L > R:
        return 0
    
    mid = (L + R) // 2
    Lmax = calcHisto(L, mid - 1)
    Rmax = calcHisto(mid + 1, R)

    Mmax = 0
    midToL = mid
    midToR = mid
    min_tall = histogram[mid]

    while(midToL >= L):
        midToL -= 1
        if(midToL >= L):
            min_tall = min(min_tall, histogram[midToL])
            tmp = (mid - midToL + 1) * min_tall
            Mmax = max(Mmax, tmp)

    while(midToR <= R):
        midToR += 1
        min_tall = min(min_tall, histogram[midToR])
        tmp = (midToR - mid + 1) * min_tall
        Mmax = max(Mmax, tmp)

    midToL = mid
    midToR = mid

    while L <= midToL or midToR <= R:
        if (L <= midToL):
            midToL -= 1

        if (midToR <= R):
            midToR += 1

        min_tall = min(min_tall, min(histogram[midToL], histogram[midToR]))
        tmp = min_tall * (midToR - midToL + 1)
        Mmax = max(Mmax, tmp)

    return max(Lmax, Rmax, Mmax)