문제 설명

해당 문제는 주어진 히스토그램에서 가장 큰 직사각형을 구해서 출력하는 문제이다.

문제 풀이

이 문제는 풀이 방법이 다양한데 일반적으로 분할 정복, 스택 그리고 스위핑 알고리즘으로 풀이가 가능하다.
여기서는 스택을 활용하여 문제를 해결하였다.

 

문제는 간단하다. 가장 큰 직사각형을 구해야 하는데, 직사각형은 보통 밑변 혹은 높이가 클수록 커진다.
그렇기 때문에 밑변이나 높이가 가장 큰 값을 기준으로 비교를 계속해야 한다.

 

따라서 가장 큰 높이나 밑변을 구하기 위해 스택을 활용하는데, 입력받은 히스토그램을 순회하면서 현재 위치를 스택에 푸시한다.
현재 위치는 나중에 밑변을 구하기 위함이고 while을 통해 스택의 top에는 점점 증가하는 히스토그램의 높이 값을 갱신한다.

 

현재 스택의 히스토그램의 top 위치의 높이 값보다 작은 히스토그램 높이 값이 들어오면 현재까지 중복된 밑변과 높이가 있기 때문에 while 내에서 pop을 하면서 히스토그램의 top 위치의 값을 현재까지의 높이 현재 위치 i 값과 top의 위치 값을 뺀 밑변 값에 곱하여 직사각형의 넓이를 구한다.

 

결국에 while을 통해 계속 직사각형의 넓이를 구하여 가장 큰 직사각형의 값을 구할 수 있다.

소스 코드

문제 : [BOJ] 1725. 히스토그램

 

1725번: 히스토그램

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

www.acmicpc.net

/*
[boj] 1725. 히스토그램
https://www.acmicpc.net/problem/1725
*/

#include <bits/stdc++.h>
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
int N;
ll ans;
vector<ll> v;
int main() 
{
    io;
    cin >> N;
    v.resize(N+1);
    for(int i=0;i<N;i++) {
        cin >> v[i];
    }
    v[N] = 0;
    stack<ll> s;
    for(int i=0;i<=N;i++) {
        while(!s.empty() && v[s.top()] >= v[i]) {
            ll cur = s.top();
            s.pop();
            int w;
            if(s.empty()) w = i;
            else w = (i - s.top() - 1);
            ans = max(ans, v[cur] * w);
        }
        s.push(i);
    }
    cout<<ans<<"\n";
    return 0;
}

+ Recent posts