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

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입출력

• 예제 입력 1

7
2
1
4
5
1
3
3

• 예제 출력 1

8

Solution

예전에 죽어라 풀려고 노력했으나 뭐가 문제였는지 잘 몰랐던 문제. 이제서야 풀게 된 소감은 참...어지럽구나 싶다.

#include <iostream>
#include <stack>
using namespace std;

int arr[100002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    int answer = 0;
    stack<int> stk;
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    
    stk.push(0);

    for(int i = 1; i <= N+1; i++ ){
        while(!stk.empty() && arr[stk.top()] > arr[i]){
            int height = arr[stk.top()];
            stk.pop();
            int width = i -  stk.top() - 1;
            answer = max(answer, height * width);
        }
        stk.push(i);
    }
    cout << answer << '\n';
}

생각보다 간단하다. 스택을 활용하면 되는 문제다.
우선 모든 값들을 배열이든 벡터든 저장 해 둔다.
아 참고로 가변 배열같은 경우엔 메모리 할당하는 정도가 갈 수록 배수로 커지기 때문에 최대로 들어올 데이터가 얼마인지 아는 경우에는 그 만큼만 할당하는 게 메모리 관리 차원에서 유리하다.

그 후 스택에 우선 0을 집어넣는다. 가장 초기에 0층부터 시작한다는 의미다.

스택에서는 막대의 인덱스를 저장한다. 인덱스 순서대로 push 하되, push 하려는 막대의 높이가 현재 스택에 가장 위에 들어있는 인덱스의 막대 높이보다 크거나 같다면 계속해서 쌓는다. 하지만 작아진다면, 현재 인덱스에 높이보다 top에 있는 인덱스의 높이가 작아질때까지 pop을 하면서 너비를 구한다.
그 중 최댓값을 answer 변수에 갱신시키는 게 전부다.

생각보다 너무 간단하게 풀린다. 과거에 비슷하게 stack으로 지지고 볶다가 포기했던 문제였는데 조금 더 편하게 생각하면 풀리는 문제였다.