BOJ

백준 6549 - 히스토그램에서 가장 큰 직사각형

yanJuicy 2020. 3. 27. 22:57
반응형

문제

 

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

 

6549번: 히스토그램에서 가장 큰 직사각형

문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이

www.acmicpc.net

 

 

풀이

 

스택을 이용하여 해결할 수 있는 문제다. 스택에는 배열의 인덱스를 저장한다. 배열의 값이 증가하는 경우면 스택에 인덱스를 차례대로 저장한다. 높이가 증가하는 경우 이전 사각형은 다음 사각형 안에도 포함될 수 있다. 반대로 배열의 값이 감소하는 경우에는 직사각형의 넓이를 구해야한다. 이전 사각형이 다음 사각형 안에 포함될 수 없기 때문이다. 

 

높이 정보를 저장한 배열을 a라 한다. 스택의 top에는 이전 사각형의 인덱스 번호가 들어있다. 따라서 넓이를 구하려는 사각형의 높이 h = a[stack.top()]이 된다. 그 후 스택의 top을 pop해준다. 사각형의 가로는 현재 인덱스 i를 이용해서 구한다. i - stack.top() - 1을 해주면 넓이를 구하려는 사각형의 가로 길이가 나오게 된다. 구한 가로 세로 길이를 이용해서 가장 큰 넓이를 가지는 사각형을 찾으면 된다.

 

그리고 반복문이 다 돌고 난 이후 스택에 인덱스 값이 남아 있을 수 있다. 이 때는 가로 길이를 n으로 하고 위에 과정을 반복하면 위에서 구하지 못한 사각형들의 넓이를 구할 수 있다. 

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <stack>
 
using namespace std;
 
int n;
int a[100000];
stack<int> st;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    while (true)
    {
        cin >> n;
        if (n == 0break;
        long long max = 0;
 
        for (int i=0; i<n; i++cin >> a[i];
 
        for (int i=0; i<n; i++
        {
            while (!st.empty() && a[i] < a[st.top()])
            {
                long long h = a[st.top()];
                st.pop();
                long long l = i;
 
                if(!st.empty()) l = i-st.top()-1;
                if (max < l*h) max = l*h;
            }
            st.push(i);
        }
 
        while (!st.empty())
        {
            long long h = a[st.top()];
            long long l = n;
            st.pop();
            if (!st.empty()) l = n-st.top()-1;
            if (max < l*h) max = l*h;
        }
        cout << max << '\n';
    }
 
    return 0;
}
cs
반응형

'BOJ' 카테고리의 다른 글

백준 2447 - 별찍기 - 10  (0) 2020.04.06
백준 14503 - 로봇 청소기  (0) 2020.04.03
백준 11729 - 하노이 탑 이동 순서  (0) 2020.03.24
백준 1107 - 리모컨  (0) 2020.03.24
백준 1780 - 종이의 개수  (0) 2020.03.23