티스토리 뷰



분할 정복법을 배운 후 푼 문제


#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
  
long long n, arr[100001];
long long histogrm() {
    long long i, ret = 0;
    stack<long long>st;
    // 스택에 왼쪽 끝 인덱스 값을 미리 삽입
    st.push(-1);
    for (i = 0; i < n; i++) {
        // 스택이 비어있지 않고
        while (!st.empty() && arr[i] < arr[st.top()]) {
            //right는 i
            int tmp = st.top();
            st.pop();
            if (!st.empty()) {
                //left는 st.top
                //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이
                ret = max(ret, arr[tmp] * (i - st.top() - 1));
            }
        }
        // 너비를 다 구하고 다음 판자를 스택에 삽입
        st.push(i);
    }
    // 히스토그램을 끝까지 스택에 넣었는데도 안끝났을때
    // 스택에 남아있는 판자들에서의 최대값을 구한다.
    while (!st.empty()) {
        int tmp = st.top();
        st.pop();
        if (!st.empty())
            ret = max(ret, arr[tmp] * (i - st.top() - 1));
    }
    return ret;
}
void init() {
    long long i=0;
    for (i = 0; i < n; i++) {
        arr[i] = 0;
    }
}
int main() {
    while (1) {
        scanf("%lld", &n);
        init();
        if (n == 0)
            break;
        else {
            for (int i = 0; i < n; i++) {
                scanf("%lld", &arr[i]);
            }
            printf("%lld\n", histogrm());
              
        }
    }
    return 0;
}


'프로그래밍 > 알고리즘' 카테고리의 다른 글

방속의 거울 문제(codeground)  (0) 2016.11.26
편집 거리 알고리즘 및 LCS문제  (0) 2016.11.26
위상정렬로 문제풀기  (0) 2016.11.22
소수의 곱(우선순위 큐)  (0) 2016.11.22
우선순위큐  (0) 2016.11.21
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
TAG
more
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함