[분할정복, 스택] 백준 6549번 히스토그램에서 가장 큰 직사각형 with Python3 ★★★

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

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

문제

각 정답자의 포스트에 잘 설명되어있다.

하지만 정말 답안이 어질어질하다...

 

 

정답 풀이 -분할정복-

import sys

# l = 직사각형 리스트의 제일 왼쪽, R= 제일 오른쪽


def max_square(l, r):
    # 리스트 h 길이가 1일 경우 그 길이를 바로 리턴
    if l == r:
        return h[l]

    else:
        mid = (l + r)//2

        # 이분탐색시 반으로 갈린 중앙 지점에 맞닿아있는 두 직사각형의 넓이 = tmp
        nl = mid
        nr = mid + 1
        nh = min(h[nl], h[nr])
        tmp = nh * 2

        cnt = 2
        while True:
            # 종료조건
            if (h[nl] == 0 or nl == l) and (h[nr] == 0 or nr == r):
                # 1.h[nl] == 0: 중앙 nl의 왼쪽 직사각형이 없다는 뜻
                # 2.nl == 1: 중앙 값이 직사각형list의 제일 아래에 도착
                # 3.h[nr] , nr == r: vice versa
                break
            elif h[nl] == 0 or nl == l:
                # nl(mid)오른쪽에는 원소가 남아있다는 조건
                if h[nr + 1] < nh:
                    nh = h[nr + 1]
                    # 그렇다면 경계면의 직사각형만들기를 중앙 오른쪽 직사각형의 오른쪽과 하라는뜻
                nr += 1
            elif h[nr] == 0 or nr == r:
                if h[nl-1] < nh:
                    nh = h[nl - 1]
                nl -= 1

            else:
                if h[nl - 1] > h[nr + 1]:  # 왼쪽 편에 있는 직사각형이 오른쪽보다 클 경우
                    if h[nl - 1] < nh:  # 그리고 중앙보다 작을 경우 / 그래야 연속적으로 합칠 수 있으니
                        nh = h[nl - 1]
                    nl -= 1  # 그리고 왼쪽아래로 탐색 진행
                else:
                    if h[nr + 1] < nh:
                        nh = h[nr+1]
                    nr += 1

            cnt += 1
            tmp = max(tmp, nh * cnt) 
        return(max(max_square(l, mid), max_square(mid+1, r), tmp))


while True:
    h = list(map(int, sys.stdin.readline().split()))
    if h[0] == 0:  # h[0]은 직사각형의 개수
        break
    print(max_square(1, len(h) - 1))

출처:https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-6549-%ED%9E%88%EC%8A%A4%ED%86%A0%EA%B7%B8%EB%9E%A8%EC%97%90%EC%84%9C-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

해석

최대한 코드를 해석해봤다. 분할 정복 개념은 간단한데 구현하는 과정들을 보면 상황에 따라 정말 다양해지는것 같다.

이경우 중앙, 왼쪽의 최대 직사각형, 오른쪽의 최대 직사각형을 구하는 여러 과정이 들어있다. 

 

 

 

 

정답 풀이 -스택-

import sys
while True:
    tmp = list(map(int, sys.stdin.readline().split()))
    if tmp[0] == 0:
        break
    max = tmp[0]
    for i in range(tmp[0]):
        for j in range(2, tmp[i + 1] + 1):
            k = 1
            while True:
                try:
                    if j <= tmp[i + k + 1]:
                        k += 1
                    else:
                        break
                except:
                    break
            if k * j > max:
                max = k * j
    print(max)

출처:https://atgane.github.io/%EB%B0%B1%EC%A4%80/%EC%8A%A4%ED%83%9D/2021/02/10/%EB%B0%B1%EC%A4%80-6549-%ED%8C%8C%EC%9D%B4%EC%8D%AC.html

 

해석