백준 / 히스토그램에서 가장 큰 직사각형 / 6549번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 히스토그램에서 가장 큰 직사각형 / 6549번 (플래티넘 5단계)

문제 사이트: https://www.acmicpc.net/problem/6549

 

문제 설명

---

나의 풀이

def solution(histogram):
    answer = 0

    # 메모이제이션
    dp = [0] * (len(histogram))

    width = 1  # 너비
    before_high = 0  # 이전 높이

    for i in range(len(histogram)):
        high = histogram[i]  # 높이

        # 처음 한 번만 실행
        if width == 1:
            dp[i] = high
            width += 1
            before_high = high  # 이전 높이
        else:
            if min(before_high, high) * width >= high:
                dp[i] = min(before_high, high) * width
                width += 1
                before_high = min(before_high, high)
            else:
                dp[i] = high
                width = 2  # 다시 시작시 2부터 시작
                before_high = high

    answer = max(dp)

    return answer


def main():
    # 결과
    result = []

    while True:
        # 테스트 케이스
        t = list(map(int, input().split()))

        if t[0] == 0:
            break
        else:
            result.append(solution(t[1:]))

    for i in result:
        print(i)

if __name__=="__main__":
    main()

메모이제이션을 이용하여 이전의 결과 값을 이용하여 풀려고 했지만 문제의 조건에 맞지 않는 풀이로 틀렸습니다.

# 정답 코드
def solution(histogram):
    stack = []  # 인덱스를 저장하는 스택
    max_area = 0  # 최대 직사각형 넓이
    histogram.append(0)  # 마지막에 0을 추가하여 남은 요소를 처리하기 쉽게 함

    for i in range(len(histogram)):
        # 스택이 비어있지 않고 현재 막대가 스택 top의 막대 높이보다 낮다면 pop 진행
        while stack and histogram[stack[-1]] > histogram[i]:
            height = histogram[stack.pop()]  # pop된 높이
            width = i if not stack else (i - stack[-1] - 1)  # 너비 계산
            max_area = max(max_area, height * width)  # 최대 넓이 갱신

        stack.append(i)  # 현재 인덱스를 스택에 push

    return max_area


def main():
    # 결과
    result = []

    while True:
        # 테스트 케이스
        t = list(map(int, input().split()))

        if t[0] == 0:
            break
        else:
            result.append(solution(t[1:]))

    for i in result:
        print(i)

if __name__=="__main__":
    main()

---

※ 알아야 할 것

스택을 이용하여 새로 들어오는 막대의 높이가 더 낮으면 이전의 막대의 높이를 모두 뽑아서 계산하는 방식을 사용했습니다.