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

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

문제

---

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

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

입력

---

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

출력

---

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

---

풀이)

처음에 이분탐색인가 싶었는데, 너비 계산에 따른 높이 변화를 하기 힘들었다.

(구한 너비가 구했던 너비보다 크면, 높이를 높이는 식으로 했더니 반례 존재)

세그먼트 트리 & divide and conquer를 이용해서 풀어야 하는 문제이다.

세그먼트 트리를 만들 때에는 높이들을 배열에 저장해 두고, 

그 배열을 이용해 구간마다 가장 작은 높이를 가지는 인덱스를 저장하면 된다.

풀이 과정

1. 직사각형 높이들을 height[]배열에 저장한다.

2. 세그먼트 트리를 만든다.

3. [1 ~ n] 범위 중 최소 높이를 가지는 인덱스 i를 찾는다.

   직사각형 너비를 구한다. 너비 = height[i] * ( n - 1 + 1 )

   구한 너비가 지금까지 구한 너비보다 클 경우, 결과값 update

   i 기준으로 범위를 나눈다. [1 ~ i-1] , [i+1 ~ n]  

   또, 각 범위마다 최소 높이를 구하는 인덱스를 찾고 너비를 구한다. 

   

   범위 나눈다 -> 인덱스 찾는다 -> 범위 나눈다 -> 인덱스 찾는다 반복 (divide and conquer)

4. 지금까지 구한 최대 너비를 출력한다.

주의사항

너비 계산할 때 int형 범위를 벗어날 수 있다.

따라서 너비 자료형을 int가 아닌 long long으로 선언한다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define INF 1000000001
int height[100001];
int tree[400001];
int n;
long long result;
 
int initialize(int node,int nodeL,int nodeR) {
    if (nodeL == nodeR) return tree[node] = nodeL;
    
    int mid = (nodeL + nodeR) / 2;
    int idx1 = initialize(node * 2, nodeL, mid);
    int idx2 = initialize(node * 2 + 1, mid + 1, nodeR);
 
    if (height[idx1] < height[idx2]) {
        return tree[node] = idx1;
    }
    else return tree[node] = idx2;
}
 
int query(int L,int R,int node,int nodeL,int nodeR) {
    //현재 범위가 찾고자 하는 범위를 벗어나면
    if (R < nodeL || nodeR < L) return -1;
    //현재 범위가 찾고자 하는 범위가 안에 있다면
    else if (L <= nodeL && nodeR <= R) return tree[node];
 
    int mid = (nodeL + nodeR) / 2;
    int idx1 = query(L, R, node * 2, nodeL, mid);
    int idx2 = query(L, R, node * 2 + 1, mid + 1, nodeR);
 
    if (idx1 == -1) return idx2;
    if (idx2 == -1) return idx1;
 
    if (height[idx1] < height[idx2]) return idx1;
    else return idx2;
}
 
void find_max(int L,int R) {
    int idx = query(L, R, 1, 1, n);
    if (idx == -1) return;
 
    long long answer = (long long)height[idx] * (long long)(R - L + 1);
 
    if (result < answer) result = answer;
 
    if(idx-1 >= L) find_max(L, idx-1);
    if(idx+1 <= R) find_max(idx + 1, R);
}
 
int main() {
 
    while (true)
    {
 
        scanf("%d", &n);
        if (n == 0)break;
        int temp = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &temp);
            height[i] = temp;
        }
        initialize(1, 1, n);
        find_max(1, n);
        printf("%lld\n", result);
        result = 0;
    }
    return 0;
}