[C++]백준 - 6549번 문제

6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net)

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이 하나 주어진다.

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

이 문제는 풀기 전에 아래 링크를 한번 참고하는 것이 좋습니다.

 

[6549번] 히스토그램 문제 :: 코린이의 얕은 블로그 (tistory.com)

[6549번] 히스토그램 문제

 

2가지 풀이 방법이 있는데, 스택을 이용하거나 세그먼트 트리를 이용할 수 있습니다.

 

스택을 이용하는 편이 더 쉽다고 생각합니다.

 

저는 세그먼트트리를 이용했습니다.

 

세그먼트트리에 대한 개념은 아래 블로그를 참고합니다.

 

41. 세그먼트 트리(Segment Tree) : 네이버 블로그 (naver.com)

41. 세그먼트 트리(Segment Tree)

 

우리는 해당 문제를 풀기 위해 다음과 같은 단계를 밟을 것입니다.

 

1. 세그먼트트리를 만들어서, 노드에 해당하는 범위의 가장 높이가 작은 INDEX를 저장하기

 

2. 완성된 세그먼트 트리를 참조해서 해당 INDEX의 앞과 뒤의 범위를 쿼리하기

 

3. 앞의 범위의 최댓값, 뒤의 범위의 최댓값, 그리고 현재 범위의 너비를 구하여 가장 큰 값을 반환 (분할 정복)

 

 

1번 과정

 

- 우선, 가장 아래 LEAF 노드에는 본인의 INDEX를 그대로 넣어주면 됩니다.

 

- 다음부터는 더 낮은 높이를 가진 INDEX를 넣어주면 됩니다. 높이가 같다면, 더 작은 수를 넣습니다.

- 예를 들어, 0~1 구간에서 0은 2의 높이를 가졌고, 1은 1의 높이를 가졌으므로 1을 넣습니다.

- 그 위도 이를 반복하면 트리가 완성됩니다.

 

 

 

2번 과정

 

- 이제 완성된 트리를 바탕으로, 쿼리를 해보겠습니다.

 

- 0~6 범위를 쿼리할 경우, 트리의 Root인 1이 나옵니다.

 

 

- 만약 2~ 6의 범위를 쿼리할 경우, 2~3 노드와 4 ~ 6노드 중 더 작은 높이를 가진 값을 쿼리합니다.

 

 

 

3번 과정

 

쿼리를 하였으면 세가지 경우를 비교하여야 합니다.

 

1. 해당 범위 * 쿼리된 값의 높이

 

 

2. 왼쪽을 쿼리한 값

 

 

3. 오른쪽을 쿼리한 값

 

 

- 오른쪽은 2~6 범위입니다. 2~6 범위를 쿼리 후, 다시 왼쪽, 오른쪽으로 나누어 재귀 형식으로 구해야 합니다.

- 모든 과정을 마치면 2~6 범위의 값은 8이됩니다.

 

 

4. 세 값을 비교하여 가장 큰 값을 반환

 

- 0~6을 쿼리해서 나온 결과물들은 각각 {7, 2, 8}이므로 가장 큰 8이 답으로 나옵니다.

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

#define INF 1000000000;
typedef long long ll;

//최소 height의 index를 반환
int get_min_height(int histo[], int A, int B)
{
    if(A == -1) return B;
    if(B == -1) return A;
    return histo[A] <= histo[B] ? A : B;
}

//start ~ end만큼의 결과물을 쿼리함
int query(int histo[], int tree[], int start, int end, int left, int right, int node)
{
    //구간이 겹치지 않음
    if(right < start || end < left) return -1;
    //구간이 완전히 포함됨
    if (left <= start && end <=right) return tree[node];

    //구간이 걸쳐 있는 경우
    int mid = (start + end) / 2;
    return get_min_height(histo, query(histo, tree, start, mid, left, right, node * 2 + 1),
                            query(histo, tree, mid + 1, end, left, right, node * 2 + 2));
}

//최대값 구하기
ll get_max_area(int histo[], int tree[], int N, int left, int right)
{
    if(left == right) return histo[left];
    int min_h = query(histo, tree, 0, N-1, left, right, 0);
    ll area = (right - left + 1);
    area *= histo[min_h];
    if(min_h != left)
    {
        ll area_left = get_max_area(histo, tree, N, left, min_h - 1);
        if(area < area_left) area = area_left;
    }
    if(min_h != right)
    {
        ll area_right = get_max_area(histo, tree, N, min_h + 1, right);
        if(area < area_right) area = area_right;
    }
    return area;
}

//세그먼트 트리 만들기
int init_tree(int histo[], int tree[], int start, int end, int node)
{
    if(start == end) return tree[node] = start;
    int mid = (start + end) / 2;
    
    return tree[node] = get_min_height(histo, init_tree(histo, tree, start, mid, node * 2 + 1),
                    init_tree(histo, tree, mid + 1 , end, node * 2 + 2));
}

int main() 
{
    int N;
    scanf("%d", &N);
	while(N != 0)
	{
	    int *histo = new int[N];
	    int *tree = new int[N << 2];
	    for(int i = 0; i < N; i++) scanf("%d", &histo[i]);
	    
	    init_tree(histo, tree, 0, N-1, 0);
        printf("%lld\n", get_max_area(histo, tree, N, 0, N-1));	    
        scanf("%d", &N);
	}
	return 0;
}

 

그 외

---

세그먼트 트리의 경우, STL이 존재하지도 않고, 개념을 알고있다 해도 직접 생각하면서 만들기엔 매우 복잡하므로, 코드를 어느정도 암기해두는 것이 좋습니다.

 

이 문제는 정말 다양한 방법으로 접근해보았지만, 메모리와 시간이 입력값에 비해 굉장히 팍팍하기 때문에 검색해서 풀었습니다. 제가 푼 백준 문제 중에선 가장 어려운 것 같습니다..