글 읽기 - 반례좀 찾아주세요 ㅠㅠ

dlehdanakf 4년 전 0

기존에 올라온 질문글의 반례들을 모두 넣어봐도 제대로된 답이 출력되던데 어떤 케이스에서 정답을 맞추지 못하는건지 도저히 감이 안잡힙니다.

미리 감사합니다!

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;

int main(void) {
    int n;
    int a[100000];


    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    stack<int> _height;
    stack<int> _index;

    int last_height = a[0];
    int answer = a[0];
    _height.push(a[0]);
    _index.push(0);

    for(int i = 1; i < n; i++) {
        if(a[i] > last_height) {
            _height.push(a[i]);
            _index.push(i);
        } else if(a[i] < last_height) {
            int stack_height, stack_index;
            while(_height.empty() == false) {
                stack_height = _height.top();
                stack_index = _index.top();

                int exclude_square = (i - stack_index) * stack_height;
                int include_square = (i - stack_index + 1) * min(stack_height, a[i]);
                answer = max(answer, max(exclude_square, include_square));
                if(stack_height <= a[i]) {
                    break;
                }

                _height.pop();
                _index.pop();
            }
            if(_height.empty()) {
                _height.push(a[i]);
                _index.push(stack_index);
            }
        }

        last_height = a[i];
    }
    while(_height.empty() == false) {
        int stack_height = _height.top();
        int stack_index = _index.top();
        int include_square = (n - stack_index) * min(stack_height, last_height);
        answer = max(answer, include_square);

        _height.pop();
        _index.pop();
    }

    printf("%d\n", answer);
}

rlat302 4년 전 9

안녕하세요 ㅎㅎ

8 4 7 6 8 5 9 1 0

Output : 24

Answer : 25

입니다!

화이팅 하세요 :)

terrasphere 2년 전 0

뒷북이긴 한데 저거 Answer는 25가 아니고 28인거 같습니다

dudwls901 2년 전 0

answer 25 맞습니다.. 한참 헷갈렸네요

ggp03016 2년 전 0

답이 어떻게 25입니까... 4 * 7 = 28이 정답인데요

(8,4,7,6,8,5,9) 는 총 7개 이고 높이가 4니까 4*7 = 28이 정답이 되어야 할텐데요..

dudwls901 2년 전 0

아 왜 25인지 다시 찾았네요 ㅎㅎ
윗 분이 말씀하신 반례는 맨 앞의 8은 N입니다 막대가 아니라
8도 막대로 치고 앞에 N이 9라고 하면 말씀하신 28이 맞겠네요

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

문제

문제

출처

ICPC

반례좀 찾아주세요 ㅠㅠ

dlehdanakf 4년 전 0

rlat302 4년 전 9

terrasphere 2년 전 0

dudwls901 2년 전 0

ggp03016 2년 전 0

dudwls901 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말