[BOJ 1725] 히스토그램

1) 문제 링크

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

2) 접근

kks227님의 블로그에서 분할 정복의 예제로 배운 문제라 딱히 접근 방식이라 할 게 없었다…
이 문제를 분할 정복으로 풀 수 있겠다는 확신을 가지려면

1) 히스토그램을 쪼개도 각 구간에서 최대 넓이를 구하는 방식에 영향을 주지 않는다.
2) 최대 넓이를 구하는 구간이 정해져 있을 때, 그 구간 내의 어떤 막대에서 시작하든 최대 넓이값은 변화가 없다.

이 두 가지 생각을 증명할 수 있어야 한다고 생각한다.

그리고 histogram(s, e) 함수는 구간 $[s, e)$에 대한 것임을 항상 염두에 둘 것. 구간 $[s, e]$가 아니다!

3) 풀이

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

int N, H[100000];

int histogram(int s, int e){
    if(s == e) { return 0; }
    if(s+1 == e) { return H[s]; }

    int mid = (s+e)/2;
    int result = max(histogram(s, mid), histogram(mid, e));

    int w=1, h=H[mid], l=mid, r=mid;
    while(r-l+1 < e-s){
        int p = (l>s) ? min(h, H[l-1]) : -1;
        int q = (r<e-1) ? min(h, H[r+1]) : -1;

        if(p >= q){
            h = p;
            --l;
        }
        else{
            h = q;
            ++r;
        }
        result = max(result, ++w*h);
    }
    return result;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> H[i];
    }
    cout << histogram(0, N);
    return 0;
}

시간복잡도는 $O(NlogN)$.

4) 피드백

gmldnd0418님의 코드.
8ms짜리이다. 0ms 수준의 코드는 입출력에서 시간을 줄인 걸로 보였고, 8ms는 stack을 이용해서 시간복잡도 $O(N)$에 푸는 코드였다.

https://j2wooooo.tistory.com/74
https://private-space.tistory.com/12

위 블로그에 자세한 설명이 있으니 참고.
핵심은 스택에 들어있는 막대보다 다음의 막대가 크거나 같으면 그냥 스택에 넣고, 그게 아니라면 현재 들어있는 막대 중 다음에 넣을 막대보다 큰 막대들을 전부 빼내며 넓이를 계산한 후 스택에 넣는 것이라고 한다.

이런 식으로 쓰-윽 쓸고 지나가면서 해를 구하는 알고리즘을 스위핑 알고리즘이라고 한다. 그리디 알고리즘의 일종인 듯…?