히스토그램( BOJ 1725 )

문제 : https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

문제 파악하기

히스토그램(막대 그래프) 내부의 가장 큰 직사각형의 넓이를 구하는 문제입니다. 중첩 반복문을 사용해서 나올 수 있는 모든 구간의 내부 직사각형을 구할 수도 있지만 N의 크기가 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 여러 가지 효율적인 알고리즘 중에서 가장 기본적인 방법인 분할 정복을 활용해서 문제를 풀어봅시다.

 

문제 해결하기

분할정복이란 말을 들어보면 뭔가 어려운 느낌이 들기에 이름은 생각하지 말고, 문제를 해결할 수 있는 방법에 집중해봅시다. 우리가 원하는 건 구간 [1, N] 내부의 가장 큰 직사각형의 넓이입니다. 그럼 [1, N]에서 나올 수 있는 가장 큰 직사각형을 구간의 중간값을 기준으로 생각해봅시다. 구간의 중간값을 mid((1+N)/2)라고 할 때, 나올 수 있는 내부의 직사각형은 mid를 기준으로 3가지 경우로 나눌 수 있습니다. 첫 번째, mid 기준 왼쪽에서 만들어지는 경우입니다. 이 경우는 구간 [1, mid-1]에서 만들어지게 됩니다. 두 번째, mid 기준 오른쪽에 있는 경우입니다. 이 경우 역시 이전과 비슷하게 구간 [mid+1, N]에서 만들어지게 됩니다. 세 번째, mid를 포함해서 만들어지는 경우입니다. 이 경우에는 구간 [1, N]에서 만들어지게 됩니다. 따라서, 우리는 위의 3가지 경우에서 만들어지는 사각형의 넓이 중 가장 큰 넓이를 구하면 됩니다. 그럼 각각의 경우를 어떻게 구할 수 있는지 살펴봅시다.

 

우리는 첫 번째와 두 번째 경우를 구하기 위해 반복적으로 특정 구간 [A, B]에 있는 가장 큰 직사각형의 넓이를 구해야합니다. 그렇기에 함수를 하나 만들어서 반복적으로 구해봅시다. 넓이를 구할 때 필요한 정보는 구간의 시작 지점과 종료 지점만 필요하기에 다음과 같이 함수를 만들 수 있습니다.

sv( int l, int r ) >> l: 구간의 시작 지점 / r: 구간의 종료 지점

 

위와 같이 함수를 만들면 첫 번째와 두 번째 경우는 쉽게 구할 수 있습니다. 첫 번째 경우는 구간 [1, mid-1]에서 나올 수 있는 가장 큰 직사각형의 넓이을 구하는 경우입니다. 이는 sv(1, mid-1)을 호출하면 구할 수 있습니다. 두 번째 경우는 구간 [mid+1, N]에서 나올 수 있는 가장 큰 직사각형의 넓이를 구하는 경우입니다. 이전 경우와 마찬가지로 sv(mid+1, N)을 호출하면 쉽게 구할 수 있습니다. 이렇게 함수를 설계하면 첫 번째와 두 번째 경우를 모두 구할 수 있습니다. 여기서 문득 궁금증이 생길 수 있습니다. sv(1, mid-1)은 어떻게 구할 수 있을까요? 이는 우리가 위에서 sv(1, N)을 구했던 방법과 동일하게 구하면 됩니다. 모든 구간에서 나올 수 있는 직사각형의 유형은 항상 3가지밖에 없으며, 우리는 모든 구간을 중간값을 기준으로 절반씩 나눠서 살펴보면 됩니다.

 

물론 무작정 절반씩 계속 나누면 함수는 종료하지 않아서 오류가 생길 수 있습니다. 따라서 우리는 적절한 종료 조건을 생각해야 합니다. 함수가 어떤 경우에는 더이상 범위를 나누지 않고 값을 한번에 구할 수 있을까요? 그런 경우는 딱 2가지 있습니다. 첫 번째, 구간의 시작 지점이 종료 지점보다 큰 경우입니다. 이 경우에는 올바르지 못한 탐색이기에 0을 반환하면 됩니다. 두 번째, 구간의 시작 지점과 종료 지점이 동일한 경우입니다. 이 경우에는 하나의 값만을 가지고 있기에 현재 위치의 사각형 넓이를 반환하면 됩니다. 물론, 종료 지점과 시작 지점이 딱 1만큼 차이가 나는 경우에 따로 값을 계산해주는 방법도 있습니다. 어떤 방법이든 편한 방법을 사용하면 됩니다.

 

종료 조건까지 만들었다면 우리는 현재 구간을 절반씩 나눠서 만들 수 있는 직사각형 넓이의 최댓값을 구했습니다. 여기에 우리가 모든 구간마다 따로 구해야하는 값이 있습니다. 바로 세 번째 경우, 중간값을 포함한 직사각형의 넓이 중 가장 큰 값입니다. 이 경우는 중간값(mid)를 기준으로 사각형을 왼쪽/오른쪽으로 확장하면서 만들어진 사각형 넓이의 최댓값을 구하면 됩니다. 여기서 중요한 점은 사각형을 확장할 경우에는 더 큰 값부터 확장해야 한다는 점입니다. 그래야 최댓값을 구할 수 있습니다. 이렇게 3가지 경우에 대해 모두 구한 다음, 그 중에서 가장 큰 값을 출력하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100010
#define MAX 1000000000
#define lint long long int
using namespace std;
 
int N;
lint inp[NMAX];
 
lint sv(int l, int r) {
    if(l>r) return 0;
    else if(l == r) return inp[l];
    else {
        lint ret, tmp;
        int ll, rr, mid;
 
        ret = 0;
        tmp = MAX;
        mid = (l + r) / 2;
        ll = rr = mid;
 
        // 중간값을 포함한 사각형
        while(1) {
            tmp = min(tmp, min(inp[ll], inp[rr]));
            ret = max(ret, tmp*(rr - ll + 1));
 
            if (ll == l and rr == r) break;
            else if (ll == l) rr++;
            else if (rr == r) ll--;
            else {
                if (inp[ll-1] > inp[rr+1]) ll--;
                else rr++;
            }
        }
 
        // mid값 기준 왼쪽/오른쪽에 위치한 사각형
        ret = max(ret, max(sv(l, mid-1), sv(mid+1, r)));
 
        return ret;
    }
}
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%lld", &inp[i]);
 
    printf("%lld", sv(1, N));
}

후기

여러가지 방법으로 해결할 수 있는 문제입니다. 최솟값을 구할 때 세그먼트 트리를 사용할 수도 있으며, 스택을 사용하여 선형 알고리즘으로도 해결할 수 있으니 여러 알고리즘을 연습할 때, 소개할만한 문제라고 생각합니다. 개인적으로는 분할 정복을 연습하기에 적절한 문제라고 느끼고 있습니다.