백준 1725번 히스토그램: C언어 풀이

백준 1725 히스토그램 문제 C언어 해설입니다.
백준 6549 히스토그램에서 가장 큰 직사각형 문제와 거의 완벽히 동일한 문제입니다.
오름차순으로 구성된 스택에 높이와 너비를 가지는 구조체를 저장하여 히스토그램내 직사각형의 최대 넓이를 구하는 방법을 상세히 설명합니다.

전략

오름차순 스택

오아시스 재결합문제와 유사하다.
막대 그래프를 높이와 너비를 가지는 구조체로 정의한다. 막대는 스택에 저장해준다.
막대 하나의 너비는 1이고, 연속한 같은 높이의 막대는 그 만큼의 너비를 가진 하나의 막대로 취급한다.

스택안에 높이 3, 5, 6, 7인 막대들이 들어가 있다고 하자.
이후 높이 4인 막대가 나타나면, 3과 4 사이 5, 6, 7은 더 이상 새로운 직사각형을 만드는 데 기여하지 못한다.
정확히는 5, 6, 7에서 높이 4까지는 이후 등장할 막대의 높이에 따라 직사각형을 구성할 수 있다.
하지만 4보다 높은 부분은 더이상 다른 막대와 합쳐져 직사각형을 만들 수 없다.

대강의 흐름은 다음과 같다.

따라서 5, 6, 7 은 이제부터 4의 높이를 가진 막대로 취급해도 무방하다.
각각의 너비인 1, 1, 2 와 새로운 너비1, 높이 4의 막대를 합쳐 너비 5, 높이 4인 구조체를 스택에 넣어준다.

이를 끝까지 반복하며 최대 넓이를 업데이트하면 된다.

코드

#include <stdio.h>

#define MAX_STACK_SIZE 100000
#define EMPTY -1

struct box
{
    int height;
    int width;
};

int main(void)
{
    int num_boxes;
    scanf("%d", &num_boxes);

    struct box stack[MAX_STACK_SIZE];
    int top = EMPTY;
    long max_area = 0;

    for (int i = 0; i < num_boxes; i++)
    {
        struct box new_box;
        scanf("%d", &new_box.height);
        new_box.width = 1;

        // Boxes with higher height does not affect the area from now
        // Thus calcuate the area & pop, compare with max_area
        // Merge the lower part with the current box
        int width = 0;
        while (top != EMPTY && stack[top].height >= new_box.height)
        {
            if (stack[top].height != new_box.height)
            {
                width += stack[top].width;
                long current_area = (long) width * stack[top].height;
                max_area = max_area > current_area ? max_area : current_area;
            }

            // Merge
            new_box.width += stack[top].width;
            top--;
        }

        // Push
        stack[++top] = new_box;
    }

    // Calcuate the rest of the area
    int width = 0;
    while (top != EMPTY)
    {
        width += stack[top].width;
        long current_area = (long) width * stack[top].height;
        max_area = max_area > current_area ? max_area : current_area;
        top--;
    }
    printf("%ld\n", max_area);
}

max_area 가 long임에 주의