글 읽기 - 수없이 시도해봤는데 틀린 이유를 모르겠습니다.

muscj7 5년 전 0

스택 그리고 길이가1인 직사각형 넓이, 스틱 하나가 이전까지 쌓인 직사각형의 넓이보다 크면 최대값을 갱신하고 그 스틱을 스택에 넣어서 또 다른 최대값을 구하는 방식을 구현했습니다.

결과적으로 어디가 틀렸는지 모르겠습니다..

#include <iostream>
#include <stack>
using namespace std;

stack<long long int> stk;

int main()
{
	long long int N, h, width, widthFor1;
	long long int ans, ansFor1;
	while (true) {
		cin >> N;
		if (N == 0) break;

		width = 0;
		ans = ansFor1 = 0;
		for (int i = 0; i < N; i++) {
			cin >> h;
            if(stk.empty()) stk.push(0);
          
            if (h  == 0) { 
                ansFor1 = ansFor1 > widthFor1 ? ansFor1 : widthFor1;
                stk.pop();
                stk.push(h);
                width = widthFor1 = 0;
            }
            else {
                width++;
                widthFor1++;
                if (stk.top() < h) {
                    if (stk.top() * width <= h) {
                        stk.pop();
                        stk.push(h);
                        width = 1;
                    }
                
                }
                else {
                    if (h * width < stk.top() * (width - 1))
                        ans = ans > stk.top() * (width - 1) ? ans : stk.top() * (width - 1);//max(ans, stk.top() * (width - 1));

                    stk.pop();
                    stk.push(h);
                } 
            }       
		}
		long long int out = ans > stk.top() * width ? ans : stk.top() * width; 
        out = out > ansFor1 ? out : ansFor1;
		cout << out << "\n";
	}

	return 0;
}

djm03178 5년 전 1

1 0

과연 이 때 widthFor1의 값은 무엇이었을까요?

muscj7 5년 전 0

widthFor1이 초기화돼있지 읺아서 0으로 초기화해주었습니다. 그래도 틀리네요.. ㅠ ㅠ

djm03178 5년 전 0

그런 방법으로 과연 풀리는 문제인지 모르겠습니다.

5 1 4 1 1 1

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

문제

문제

출처

ICPC

수없이 시도해봤는데 틀린 이유를 모르겠습니다.

muscj7 5년 전 0

djm03178 5년 전 1

muscj7 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말