[백준 1725번] [스택] 히스토그램

Approach

기본적인 접근 방법은 다음 블로그를 참고하면 된다.

https://cocoon1787.tistory.com/315

[C/C++] 백준 1725번 - 히스토그램 (스택 풀이)

이 접근방법을 잘 곱씹어보면, 스택이 점점 쌓여감에 따라서 들어있는 숫자들을 index로 가지는 히스토그램 막대의 높이는 계속 증가하거나 같을 수 밖에 없다.

 

따라서 pop 연산을 계속 수행하게 되면, 나오는 숫자들은 계속 감소하거나 같을 수 밖에 없다.

위 블로그에 나온 예시에서 불연속점이 언제 발생하는지를 잘 곱씹어보면, 일종의 히스토그램 막대의 높이가 꺾이는 지점이라는 것을 알 수 있다. 즉, 스택에 저장된 값에 무조건 꺾이는 점이 존재할 수 밖에 없다.

 

따라서 직사각형의 넓이를 구할 때  h[check]*(i - s.top() - 1) 인 것이다.

(꺾이는 후보 바로 직전까지는 무조건적으로 높이가 유지되는 것이 보장되기 때문이다.)

 

혹자는, 스택을 pop함에 따라 막대의 높이가 같을 수도 있으므로 해당 지점을 포함해야하는 것은 아닌지에 대해 의구심을 가질 수 있다.

하지만, 문제 특성상 막대의 높이가 유지되다가 감소되는 지점은 반드시 index 차이가 1개 발생할 수 밖에 없다. 따라서 추가적으로 해당 과정을 반복하면서 자연스럽게 고려하게 되므로 굳이 신경쓰지 않아도 되는 것이다.

 

추가적으로 이 문제의 풀이방법은 여러 개 존재하는데, 대표적으로 분할정복과 세그먼트 트리가 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void)
{
    int v[100002];
    memset(v, 0, sizeof(v));
    fastio;
    int n;
    stack<int> s;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }

    s.push(0);
    int max_value = 0;

    for (int i = 1; i <= n + 1; i++)
    {
        if (v[s.top()] <= v[i])
        {
            s.push(i);
        }
        else
        {
            while (true)
            {
                if (v[s.top()] > v[i])
                {
                    int cmp = s.top();
                    s.pop();
                    max_value = max(max_value, v[cmp] * (i - s.top() - 1));
                }
                else
                    break;
            }
            s.push(i);
        }
    }

    cout << max_value << "\n";
    return 0;
}