글 읽기 - 1725번 히스토그램 반례 부탁드립니다.

dearsanta 7년 전 0

테스트 케이스는 통과하는데 어떤 반례가 있고 원인이 무엇인지 모르겠습니다.

#include <cstdio>
#include <stack>
#include <vector>
#define MAX 100000

typedef unsigned long long int uInt64;
using namespace std;

vector<int> h;

int Max(uInt64 a, int b)
{
    return a > b ? a : b;
}

uInt64 solveStack()
{

    int n;
    scanf("%d", &n);

    uInt64 ret = 0;
    stack<int> s; // 스택


    for (int i = 0; i < n; i++) // 입력 받기
    {
        int a;

        scanf("%d", &a);
        h.push_back(a);
    }

    h.push_back(0);

    for(int i = 0; i < h.size(); i++)
    {

        while(!s.empty() && h[s.top()] >= h[i])
        {
            int j = s.top();
            s.pop();

            int width = 1;

            if (!s.empty())
                width = (i - s.top() - 1);

            ret = Max(ret, width * h[j]);
        }

        s.push(i);

    }

    return ret;
}


int main()
{

    printf("%lld", solveStack());

    return 0;
}

dearsanta 7년 전 2

자답합니다.

39 line while문 내부에서 스택이 비었다는건 j가 0 번째 막대부터 i - 1 번째 막대까지 중 가장 작다는 것이므로

width 는 1이 아니라 i 가 되는 것입니다.

stack : 2 3 4 0

stack : 2 3

stack : 2

j = 0;

stack : empty

위와 같기 위해서는 h[i] == 0

이여야함으로

i 는 3 입니다.

3 * h[j]

h[j] == 2;

즉 2를 최대로 하는 사각형은 3 * 2 = 6 입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1725번 히스토그램 반례 부탁드립니다.

dearsanta 7년 전 0

dearsanta 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말