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

문제

백준 6549

방법 1

설명

세그먼트 트리로 구간의 최솟값을 구한다. 그리고 각 위치마다 자신의 높이 이상인 연속적인 구간을 이분탐색을 통해서 구한다. 이때 좌우를 구해서 더해줘야지 한쪽만 구하면 안된다.

9
5 2 4 2 3 2 4 2 5 

위와 같은 경우에 높이를 2로 통일하면 최댓값 18 이 되는 것이 그 반례이다. 높이가 2 인 지점에서 좌우로 탐색하지 않으면 16 이상의 값을 얻을 수 없다.

위 코드에서는 Calc() 로 왼쪽넓이를 구했고 Calc2() 로 오른쪽 넓이를 구했다. 자기 자신의 바의 넓이는 Calc() 에서 가로를 1 더해서 조절했다.

시간 복잡도

O(\(N (\log{N})^2\))

코드

using ll = long long;
ll n;

template<typename T, size_t _H>
class SegmentTree
{
	template<typename F>
	struct Node {
		Node() {}
		Node(F v) : v(v) {}
		F operator+(const Node& in) { return  min(v, in.v); }
		F v = 3e9;
	};

public:
	void Init() { for (int i = INDEX_MAX - 1; i > 0; i--) nodes[i] = nodes[i << 1] + nodes[i << 1 | 1]; }

	void Update(int i, const T& v) {
		for (i += INDEX_MAX - 1, nodes[i] = v; i > 1; i >>= 1)
			nodes[i >> 1].v = nodes[i] + nodes[i ^ 1];
	}
	
	Node<T> Query(int l, int r) {
		T rs = T(3e9);
		for (r += INDEX_MAX - 1, l += INDEX_MAX - 1; l <= r; r >>= 1, l >>= 1)
		{
			if (l & 1) rs = nodes[l++] + rs;
			if (!(r & 1)) rs = nodes[r--] + rs;
		}
		return rs;
	}
	
	Node<T> nodes[1 << _H];
	int INDEX_MAX = 1 << _H - 1;
};
SegmentTree<ll, 18> seg;

ll Calc(ll in, ll h)
{
	ll res = in;
	ll begin = in, end = n;
	while (begin <= end)
	{
		ll m = (begin + end) / 2;
		ll c = seg.Query(in, m).v;
		if (c >= h) {
			res = max(res, m);
			begin = m + 1;
		}
		else end = m - 1;
	}
	return h * (res + 1 - in);
}

ll Calc2(ll in, ll h)
{
	ll res = in;
	ll begin = 1, end = in;
	while (begin <= end)
	{
		ll m = (begin + end) / 2;
		ll c = seg.Query(m, in).v;
		if (c >= h) {
			res = min(res, m);
			end = m - 1;
		}
		else begin = m + 1;
	}
	return h * (in - res);
}

int main()
{
	while (1)
	{
		cin >> n;
		if (n == 0) break;
		for (int i = 1; i <= n; i++)
			cin >> seg.nodes[seg.INDEX_MAX + i - 1].v;
		seg.Init();

		ll ans = 0;
		for (int i = n; i >= 1; i--)
			ans = max(ans, Calc(i, seg.nodes[seg.INDEX_MAX + i - 1].v) + Calc2(i, seg.nodes[seg.INDEX_MAX + i - 1].v));
		cout << ans << '\n';
	}
}

방법 2

설명

스택을 사용해서 현재 값 이상으로는 값을 다 빼고 다시 넣고를 반복한다. 이때 idx 와 h 를 같이 넣는다. 그러면 각 스택에 들어있는 연속된 원소 간의 관계는 어떻게될까? 임의의 연속된 원소를 a1, a2 라고 하자. a1.idx < a2.idx 와 a1.h < a2.h 를 만족하는 것은 자명할 것이다. 그러면 a1.idx ~ a2.idx 에 해당했던 원소는 어디로 갔을까? 그들은 a1.h 보다 컸기 때문에 중간에 pop() 당했다. 그리고 a2.h 보다 커야한다. 그들은 a2.h 보다 큰 어떤 원소에 의해서 pop() 당했고, 이 원소는 다시 a2 에 의해 pop() 당해 사라졌기 때문이다.

그러면 (a2.idx - a1.idx)*(a2.h) 가 바로 연속되고 가장 큰 직사각형이 된다. 스택에 값이 추가되기 전까지는 말이다. a2 이후에 오는 원소를 a3 라고 하자. 역시 a2.h < a3.h 를 만족할 것이다. 그러면 방금 만든 사각형을 확장해 (a3.idx - a1.idx)(a2.h) 로 만들 수 있다.

이때의 a3 은 스택의 운영에 따라 하나가 아닐 수가 있다. a3 가 추가되었다가 다음 원소에 의해 a3 만 pop()되고 a2는 살아남고 이를 반복할 수 있기 때문에다. 당연히 가장 마지막에 오는 것이 우리가 원하는 값이다. 이는 a2 를 pop() 시키는 원소의 바로 이전 값이 된다.

이러한 이유로 아래 코드가 성립된다.

세그트리와 비교하면 대략 10 배 이상 차이가 난다. 시간복잡도 상 \((\log{N})^2\) 차이가 나는걸 고려하면 당연한 결과이다. 하지만 세그트리보다 발상이 매우 어렵다.

시간 복잡도

O(N)

코드

using ll = long long;

int main()
{
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;

        ll cur, ans = 0;
        stack<pair<int, int>> st; //idx, height
        st.push({ 0, -1 });
        for (int i = 1; i <= n+1; i++)
        {
            if (i <= n) cin >> cur; else cur = 0;
            while (st.top().second >= cur)
            {
                auto a2 = st.top(); st.pop();
                auto a1 = st.top();
                ans = max(ans, (ll)(i - 1 - a1.first) * a2.second);               
            }
            st.push({ i, cur });
        }
        cout << ans << '\n';
    }
}