[C++ 백준 풀이][Platinum V] 1725번 : 히스토그램 / 6549번 : 히스토그램에서 가장 큰 직사각형

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1725번 : '히스토그램' 문제와, 6549번 : '히스토그램에서 가장 큰 직사각형' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀기 위해서 세그먼트 트리의 응용에 대해 짚고 넘어갈 것입니다. (스택으로 간단하게 풀이할 수도 있지만, 정석적으로 풀이하도록 하겠습니다.)

 

 

1725번 : 히스토그램

 

히스토그램을 N개의 줄로 입력받을 때, 히스토그램에서 가장 넓은 직사각형의 넓이를 출력하는 문제입니다.

예를 들어 위의 히스토그램에서는 3번째 그래프와 4번째 그래프에 걸쳐 가로 2, 세로 4의 직사각형이 가장 크므로 답으로 8을 출력해주어야 합니다.

이 문제를 풀이하기 위해 세그먼트 트리를 구현하고, 이를 활용해보도록 하겠습니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
using namespace std;

int N;
vector<int> Arr, Tree;

void initTree(int Begin, int End, int Node) {
    if(Begin == End) {
        Tree[Node] = Begin;
        return;
    }
    int Mid = (Begin+End)/2;
    initTree(Begin, Mid, Node*2);
    initTree(Mid+1, End, Node*2+1);
    if(Arr[Tree[Node*2]] < Arr[Tree[Node*2+1]]) Tree[Node] = Tree[Node*2];
    else Tree[Node] = Tree[Node*2+1];
}

int findMinIdx(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return -1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMinIdx = findMinIdx(Begin, Mid, Node*2, Left, Right);
    int rightMinIdx = findMinIdx(Mid+1, End, Node*2+1, Left, Right);
    if(leftMinIdx < 0) return rightMinIdx;
    if(rightMinIdx < 0) return leftMinIdx;
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return leftMinIdx;
    else return rightMinIdx;
}

int maxArea(int Left, int Right) {
    int minIdx = findMinIdx(0, N-1, 1, Left, Right);
    int Ans = (Right-Left+1)*Arr[minIdx];
    if(minIdx+1 <= Right) {
        int Area = maxArea(minIdx+1, Right);
        if(Area > Ans) Ans = Area;
    }
    if(minIdx-1 >= Left) {
        int Area = maxArea(Left, minIdx-1);
        if(Area > Ans) Ans = Area;
    }
    return Ans;
}

int main() {
    scanf("%d", &N);
    Arr.resize(N);
    for(int i=0; i<N; i++) scanf("%d", &Arr[i]);
    Tree.resize(N*4);
    initTree(0, N-1, 1);
    printf("%d", maxArea(0, N-1));
}

 

세그먼트 트리를 구현하는 것도 중요하겠지만, 이 문제를 푸는 핵심 아이디어는 다음과 같습니다.

구간 노드에 minIdx를 저장하고, minIdx를 기준으로 왼쪽과 오른쪽으로 구간을 쪼개서 재귀적으로 maxArea를 찾아가는 것입니다.

즉 단순한 구간 합 세그먼트 트리나 minTree가 아닌, minIdx를 저장하는 tree를 만들어야 합니다.

 

우선 init 과정에서 한 개짜리 구간 노드에 대해서는 그냥 Begin(주소)을 노드에 저장해줍니다.

구간 노드에 대해서는 왼쪽 트리와 오른쪽 트리로 나누어 탐색을 진행하고, 왼쪽 트리의 min이 더 작으면 왼쪽 트리의 minIdx를 저장, 오른쪽 트리의 min이 더 작으면 오른쪽 트리의 minIdx를 저장해주는 과정을 거칩니다.

 

이후 maxArea 함수를 작성할 때 minIdx를 구하는 함수를 호출해주도록 합니다.

findMinIdx 함수는 기존의 세그먼트 트리 구현의 검색 과정과 같습니다.

Left가 End보다 크거나 Right가 Begin보다 작은 구간에 대해서는 -1을 리턴하여 이후 검사할 때 -1이 나오면 구간을 벗어난 것으로 간주합니다.

Begin~End 구간이 Left~Right 구간을 포함하면 그냥 Begin~End 구간의 노드를 리턴하여 해당 구간의 최솟값을 리턴하도록 합니다.

이 경우에도 역시 반으로 쪼개서 최솟값을 탐색해주고, 최종적으로 찾은 minIdx를 리턴해주도록 합니다.

 

maxArea 함수에서는 위의 함수에서 찾은 minIdx에다가 Right-Left+1을 곱해서 최대 직사각형의 넓이를 구해줍니다.

그 다음 minIdx를 기준으로 왼쪽, 오른쪽 구간을 나누어 다시 maxArea를 수행합니다.

그 이유는 간단히 생각해보아도 알겠지만, 최대 직사각형을 만들 때 가장 방해가 되는 것은 minIdx의 min 값입니다.

따라서 기존의 min 값 없이 직사각형을 잡으면 크게 나올 가능성이 높기 때문에 위와 같이 이분적으로 탐색을 수행해줍니다.

넓이를 계산할 때마다 Ans와의 비교를 통해 max 값이 나오면 갱신해줍니다.

마지막으로 maxArea 값을 출력해주면 정답이 됩니다.

 

 

위의 풀이를 제출해보면 36ms의 짧은 시간에 문제를 해결함을 확인할 수 있습니다.

세그먼트 트리에 구간합이나 최소, 최댓값을 저장하는게 아니라 주소를 저장한다는 점에서 아이디어가 인상깊었던 문제였습니다.

 

 

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

 

한편 6549번 문제 역시 위의 문제와 비슷하기 때문에 같은 방식으로 해결이 가능합니다.

이 문제는 여러 개의 테스트케이스를 요구하기 때문에 vector의 갱신이 필요합니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
using namespace std;

int N;
vector<int> Arr, Tree;

void initTree(int Begin, int End, int Node) {
    if(Begin == End) {
        Tree[Node] = Begin;
        return;
    }
    int Mid = (Begin+End)/2;
    initTree(Begin, Mid, Node*2);
    initTree(Mid+1, End, Node*2+1);
    if(Arr[Tree[Node*2]] < Arr[Tree[Node*2+1]]) Tree[Node] = Tree[Node*2];
    else Tree[Node] = Tree[Node*2+1];
}

int findMinIdx(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return -1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMinIdx = findMinIdx(Begin, Mid, Node*2, Left, Right);
    int rightMinIdx = findMinIdx(Mid+1, End, Node*2+1, Left, Right);
    if(leftMinIdx < 0) return rightMinIdx;
    if(rightMinIdx < 0) return leftMinIdx;
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return leftMinIdx;
    else return rightMinIdx;
}

long long maxArea(int Left, int Right) {
    int minIdx = findMinIdx(0, N-1, 1, Left, Right);
    long long Ans = (long long)(Right-Left+1)*(long long)Arr[minIdx];
    if(minIdx+1 <= Right) {
        long long Area = maxArea(minIdx+1, Right);
        if(Area > Ans) Ans = Area;
    }
    if(minIdx-1 >= Left) {
        long long Area = maxArea(Left, minIdx-1);
        if(Area > Ans) Ans = Area;
    }
    return Ans;
}

int main() {
    while(1) {
        scanf("%d", &N);
        if(!N) break;
        Arr.resize(N);
        for(int i=0; i<N; i++) scanf("%d", &Arr[i]);
        Tree.resize(N*4);
        initTree(0, N-1, 1);
        printf("%lld\n", maxArea(0, N-1));
    }
}

 

코드는 위의 문제와 거의 비슷하며, 단순히 테스트케이스 부분을 while문으로 구성해준 것이 다입니다.

vector의 갱신은 resize로 해줄 수 있으며, 값의 입력은 어차피 다시 이루어지기 때문에 초기화를 해줄 필요는 없습니다.

 

 

코드를 제출해보면 위와 같이 120ms라는 짧은 시간에 문제가 해결됨을 알 수 있습니다.