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

내가 짠 코드

...

• 플이 방법을 떠올리지 못하였다.

다른 사람이 짠 코드

from sys import stdin

while True:
    graph = list(map(int, stdin.readline().split()))

    # 0이 입력되면 반복문을 종료합니다.
    if graph[0] == 0:
        break

    # 스택과 최대 직사각형 넓이를 저장할 변수를 초기화합니다.
    stack = []
    max_result = 0

    for i, height in enumerate(graph):
        if i == 0:  # 첫 번째 i는 막대기의 개수를 의미하므로 넘어갑니다.
            continue

        # 스택의 가장 위쪽 막대기보다 현재 막대기의 높이가 작으면
        if stack and stack[-1][1] > height:
            while stack:  # 스택에서 빼내며 최대 직사각형 넓이를 계산합니다.
                stack_i, stack_height = stack.pop()
                width_start = 1
                if stack:
                    width_start = stack[-1][0]+1
                result = (i - width_start) * stack_height
                max_result = max(result, max_result) # 최대값 갱신
                # 스택에 들어있는 막대 중에서 현재 막대의 길이보다 큰 것들만 꺼내서 계산합니다.
                if not stack or stack[-1][1] <= height:
                    break

        # 스택이 비어 있거나 스택의 가장 위쪽 막대기보다 현재 막대기의 높이가 크거나 같으면
        if not stack or stack[-1][1] <= height:
            stack.append((i, height))  # 스택에 현재 막대기를 추가합니다.

    # 반복이 종료되고, 스택에 남은 막대기가 있다면 계산합니다.
    while stack:
        stack_i, stack_height = stack.pop()
        width_start = 1
        if stack:
            width_start = stack[-1][0]+1
        result = (graph[0]+1 - width_start) * stack_height
        max_result = max(result, max_result) # 최대값 갱신

    # 최대 직사각형 넓이를 출력합니다.
    print(max_result)

• 리스트 0번째에 막대의 수를 담고, 이후 순차적으로 막대의 높이를 담는다.
• 리스트를 순회한다.
  • 인덱스와 높이를 같이 사용할 것이다. (현재 요소)
  • 만약 스택에 요소가 있고, 가장 뒤의 요소의 높이가 현재 요소의 높이보다 작다면,
    • 스택에서 빼내면서 빼낸 막대의 정보를 저장한다.
    • 너비의 시작지점의 기본값은 1이며(스택 안에 내용물이 없을 경우), 아직 남은 게 있을 경우 스택 맨 마지막 요소 다음 인덱스가 너비의 시작지점이다.
      • 그래프가 내림차순으로 주어질 경우, 이전 순회에서 내용물이 버려지므로 스택 맨 마지막 요소 다음으로 잡는 것이 좋다.
    • 너비의 종료지점은 현재 요소의 인덱스이다.
    • 높이는 스택에서 방금 꺼낸 것을 쓴다.
    • 높이와 너비를 곱해서 최댓값인 경우 갱신한다.
    • 다음 스택의 요소의 높이가 현재 요소의 높이보다 크다면 이를 반복하고 아니면 반복문을 종료한다.
  • 그 이후, 스택이 비어있거나(앞서서 순회한 요소가 이때 들어갈 수 있다.) 스택 가장 뒤 요소의 높이가 현재 요소의 높이보다 크거나 같다면 스택에 현재 요소를 추가한다.
• 스택에 남은 막대가 있다면 계산한다.
  • 위에서 쓴 방식과 유사하다.
  • 단 너비의 종료 지점은 그래프 전체의 다음 인덱스이다.
• 위에서 구한 최대값을 출력한다.

참고

https://e-juhee.tistory.com/entry/python-백준-6549-히스토그램에서-가장-큰-직사각형

https://codable.tistory.com/1