글 읽기 - 6549번 질문드립니다.

wlsth1004100 4년 전 0

기본적으로 stack 을 이용해서 문제를 풀었습니다.

높이가 0인경우도있어 신경을썻고 값이 int을 넘을수있어 자료형도 신경썻는데

질문게시판에 있는 예제들은 통과가 되는데 반례나 오류가있는 부분지적해주시면 감사하겠습니다.

#include<cstdio>
#include<stack>

using namespace std;

int main()
{
	
	long long int n, curHeight, pastHeight, zeroPos = 0, width, ans = 0, data[100001];
	
	bool isZero = false;
	stack<int> st;

	while (true) {
		isZero = false;
		zeroPos = 0;
		ans = 0;
		scanf("%lld", &n);
		if (n==0)
			break;
		for (int i = 0; i < n; i++) {
			scanf("%lld", &data[i]);
			curHeight = data[i];
			if (!curHeight)
				isZero = true;

			while (!st.empty() && curHeight < data[st.top()]) {
				width = i - st.top();
				pastHeight = data[st.top()];

				if (ans < width * pastHeight)
					ans = width * pastHeight;
				st.pop();
			}

			if (st.empty() && !curHeight && i>0) {
				if (ans < pastHeight * (i - zeroPos))
					ans = pastHeight * (i - zeroPos);
				zeroPos = i + 1;
			}
			else
				st.push(i);
		}

		while (!st.empty()) {
			width = n - st.top();
			int height = data[st.top()];
			if (ans < width * height)
				ans = width * height;
			st.pop();

			if (st.empty() && !isZero)
				if (ans < n*height)
					ans = n * height;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

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

문제

문제

출처

ICPC

6549번 질문드립니다.

wlsth1004100 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말