[BOJ 6549 // C++] 히스토그램에서 가장 큰 직사각형

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6549번 문제인 히스토그램에서 가장 큰 직사각형이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6549

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

이 문제는 크게 두가지 방법으로 풀 수 있음이 알려져있다. 하나는 분할정복(divide&conquer)이고, 다른 하나는 스택을 이용한 풀이방법이다.

글쓴이는 스택을 이용하여 풀어보았다.

 

가장 큰 직사각형은 그 직사각형의 좌우 막대가 직사각형의 높이보다 낮거나 그 쪽으로 더 이상 막대가 없어야하고, 그 직사각형을 구성하는 막대 중 현재 직사각형의 높이와 같은 높이인 막대가 있어야 한다.

따라서, 스택을 왼쪽의 막대서부터 읽으면서, (같거나) 높아지는 순으로 막대가 들어있게 관리하면 문제를 간단히 풀 수 있다.

 

아래는 글쓴이가 문제를 풀기 위해 사용한 코드의 설명이다.

 

pair<long long,long long>형을 저장하는 스택을 만들고, {0,0}을 저장해두자.

이 pair의 first값은 그 막대의 높이, second값은 그 막대의 가로길이를 의미한다.

 

매 밑변이 1인 직사각형의 높이를 입력받을 때마다 현재 스택의 가장 위에 놓여있는 막대보다 길이가 크거나 같다면 {막대높이, 1}을 스택에 밀어넣는다.

그렇지 않다면, 스택에서 입력받은 높이보다 높은 막대를 빼면서, 만나는 막대의 높이와 그 막대까지의 가로를 계산해 현재까지의 최대 넓이를 갱신한다. 스택에서 더 빼낼 막대가 없다면, 스택에 {입력받은 막대 높이, 빼낸 막대 가로 총합+1}을 집어넣는다.

이를 반복하면 답을 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;
using std::pair;

void solve(int N) {
    long long ans = 0;
    vector<pair<long long, long long>> stk = { {0,0} };
    for (int i = 0;i < N;i++) {
        long long current; cin >> current;
        if (current >= stk.back().first) stk.push_back({ current,1 });
        else {
            long long cnt = 0;
            while (current < stk.back().first) {
                long long height, width;
                height = stk.back().first;
                width = stk.back().second; stk.pop_back();
                cnt += width;
                if (ans < height * cnt) ans = height * cnt;
            }
            stk.push_back({ current,cnt + 1 });
        }
    }
    long long cnt = 0;
    while (0 < stk.back().first) {
        long long height, width;
        height = stk.back().first;
        width = stk.back().second; stk.pop_back();
        cnt += width;
        if (ans < height * cnt) ans = height * cnt;
    }
    cout << ans << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    while (N!=0) {
        solve(N);
        cin >> N;
    }
    
    return 0;
}