[editorial] Editorial - E. Candlestick Charts

  • Toivoa
    Toivoa

    [출제 의도]
    유명한 Largest Rectangle in a Histogram 문제(링크)에서 윗부분만이 아니라 아랫 부분의 위치도 변한다면 어떨까? 에서 시작한 문제입니다.
    이 editorial은 출제 의도에 맞춰서 위 문제의 풀이를 변형하여 풀었습니다.
    [문제 해설 - Largest Rectangle in a Historgam]
    먼저 O(N^2) 해법은 어떤 위치에서 왼쪽으로 진행하면서 그 높이 이하가 되는 시작점과 오른쪽으로 진행하면서 그 높이 이하가 되는 점을 구하고, (해당 거리 * 높이)의 계산을 통해서 풀게 됩니다.
    그러나 이런 문제를 O(N^2)으로 내지는 않겠죠? 저렇게 풀어서 낸다면 Time Limit Exceeded라는 결과를 받게 됩니다.
    여기에서 조금 더 생각해보면 높이가 계속 높아지고 있을 때에는 왼쪽으로 이동해서 찾는 시작점이 현재 점과 같다는 것을 알 수 있습니다.
    그렇다면 만약 중간에 높이가 낮아진다면 어떨까요?
    중간에 높이가 낮아진다는 것은 앞의 현재 높이보다 높았던 것들의 끝점이 현재 위치라는 것을 알 수 있습니다. 또한 지금 현재 위치의 시작점은 현재 높이보다 높아지기 시작한 점이 됩니다.
    이 성질을 이용해서 스택에 (시작점, 높이)를 계속 쌓으면서 높이가 낮아질 때 스택에서 빼면서 계산하고, 마지막으로 계산한 시작점을 현재 위치의 시작점으로 놓을 수 있습니다.
    이렇게 푼다면 앞에서부터 한번만 쭉 보면서 풀 수 있으며, 스택에 들어가고 나오는 것도 한번씩이면 되기 때문에 O(N)의 해가 됩니다.
    이를 간단히 코드로 나타낸다면 다음과 같이 됩니다.

    struct in_stack
{
        int pos, hi;
};
hi[n] = 0;
stack<in_stack> s;
for (int j = 0; j <= n; ++j)
{
        in_stack c, d;
        d.pos = j;
        while (!s.empty())
        {
                c = s.top();
                if (c.hi < hi[j]) break;
                res >?= c.hi * (j - c.pos);
                d.pos = c.pos;
                s.pop();
        }
        d.hi = hi[j];
        s.push(d);
}

    [문제 해설 - Candlestick Charts]
    히스토그램 문제와 다른 점은 아래 부분이 변한다는 것입니다.
    따라서 모든 가능한 아래 부분의 위치(?)를 다 해본다면 O(N^2)으로 풀 수 있습니다. 아래 부분의 위치를 선택했을 때 candlestick charts가 선택된 아래 부분과 만나지 않는 경우에 주의해서 풀면 위 히스토그램 문제의 풀이를 쉽게 적용할 수 있습니다.
    [spoiler="소스코드 보기"]

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
int T;
int n, m;
int low[2001], hi[2001], lo[2001];
struct in_stack
{
        int pos, hi;
};
int main()
{
        scanf("%d", &T);
        while (T--)
        {
                scanf("%d", &n);
                for (int i = 0; i < n; ++i)
                {
                        scanf("%d%d", &low[i], &hi[i]);
                        lo[i] = low[i];
                }
                sort(lo, lo + n);
                m = unique(lo, lo + n) - lo;
                hi[n] = low[n] = -1;
                int res = 0;
                for (int i = 0; i < m; ++i)
                {
                        stack<in_stack> s;
                        for (int j = 0; j <= n; ++j)
                        {
                                in_stack c, d;
                                if (lo[i] > hi[j] || lo[i] < low[j])
                                {
                                        while (!s.empty())
                                        {
                                                c = s.top();
                                                res >?= (c.hi - lo[i]) * (j - c.pos);
                                                s.pop();
                                        }
                                        continue;
                                }
                                d.pos = j;
                                while (!s.empty())
                                {
                                        c = s.top();
                                        if (c.hi < hi[j]) break;
                                        res >?= (c.hi - lo[i]) * (j - c.pos);
                                        d.pos = c.pos;
                                        s.pop();
                                }
                                if (hi[j] <= lo[i]) continue;
                                d.hi = hi[j];
                                s.push(d);
                        }
                }
                printf("%d\n", res);
        }
}

    [/spoiler]

    • 이 풀이는 JM님이 의도한 풀이가 아닐거라 생각하면서 JM님의 더 개선된 알고리즘을 이용한 editorial을 기대해봅니다.
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
2개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    참고로 >?= 연산자는 gcc의 extension이기 때문에 vc에서는 컴파일 에러가 납니다.
    a >?= b는 a = max(a, b) 의 의미입니다.


    16년 전 link
  • realmind
    realmind

    전 DP로 풀었는데 이런 방법도 있었군요..


    16년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.