6549번: 히스토그램에서 가장 큰 직사각형 (BOJ C/C++)

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

사용 언어: C++

 

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

풀이

고민을 해봤지만 잘 모르겠어서 해설을 찾아봤는데, 100% 이해한 것인지는 모르겠지만 일단 이해한데로 써보겠다.

 

답을 보면서 이해한 것은 새로운 높이를 입력받을 때마다 새로운 높이가 top 높이보다 작으면 그냥 push를 하고 그게 아니라면 스택에 저장된 높이보다 작아질 때까지 pop하면서 max 넓이를 계산하는 것이다. 그러면 입력 받은 곳의 idx부터 기존 스택에 있던 곳까지 직사각형이 만들어진다. 그렇지 못한 입력 (높이가 더 큰 입력을 받으면) 스택에서 남은 부분이 있으면 끝 idx에서 남은 스택 idx 를 빼고 높이를 곱한 넓이와 기존 max를 비교하면서 pop한다는 것이다.

 

이 코드를 이해하기 위해 여러 사람들이 써 놓은 해설을 찾아봤지만 다들 나만큼 이해를 못한 모양인지 확 와닿게 풀이를 쓴 사람이 없었다. 그러다 세그먼트 트리로 이 문제를 푸는 풀이를 발견하고 그쪽이 더 잘 이해되서 세그먼트 트리로 이 문제를 푸는 글도 올려보겠다.

// Authored by : haneulkimdev
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/d98aedfde0e444509de83f1a21c8ef7e
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    stack<pair<int, int>> S;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
      int h;
      cin >> h;
      int idx = i;
      while (!S.empty() && S.top().X >= h) {
        ans = max(ans, 1LL * (i - S.top().Y) * S.top().X);
        idx = S.top().Y;
        S.pop();
      }
      S.push({h, idx});
    }
    while (!S.empty()) {
      ans = max(ans, 1LL * (n - S.top().Y) * S.top().X);
      S.pop();
    }
    cout << ans << '\n';
  }
}

/*
스택에는 (높이, 해당 높이가 최초로 등장한 위치)가 저장된다. 기본적으로 스택은
높이에 대한 monotone stack으로 관리된다. 스택에서 pop이 발생할 때 마다 현재
스택의 top을 가지고 만들 수 있는 직사각형의 넓이를 계산할 수 있다.
long long으로의 형변환을 편하게 처리하기 위해 1LL을 매번 곱했고, 그냥 스택
자체를 pair<long long, long long>으로 선언해도 크게 상관 없다.
*/