글 읽기 - 옥상정원 반례를 못찾겠습니다ㅠ

kih629 4년 전 0

처음에 높이를 다 받고, 뒤쪽부터 스택에 넣으면서 비교 대상이 스택에 있는 빌딩보다 크면 스택에 있는 빌딩을 빼고 비교 대상을 넣는 식으로 짰는데 어느 부분이 문제인지 모르겠습니다....

#include <bits/stdc++.h>
using namespace std;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, h, ans = 0, max=0;
	vector<int>v;
	stack<pair<int, int>>k;

	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> h;
		v.push_back(h);
		if (h > max)max = h;
	}

	k.push(make_pair(max+1, n));

	for(int i=n-1;i>=0;i--) {
		while (!k.empty()) {
			if (k.top().first >= v.back()) {
				ans += k.top().second - i-1;
				break;
			}
			k.pop();
		}
		k.push(make_pair(v.back(), i));
		v.pop_back();
	}
	cout << ans;
}

stature_lee 3년 전 2

답의 크기가 int 자료형이 표현하는 범위를 넘어서 틀리신 것 같습니다.

작성하신 코드에서 ans 자료형을 long long int로 바꾸고 제출하니 맞았다고 나오네요.

kih629 3년 전 0

헐 감사합니다ㅠㅠㅠ

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

문제

문제

출처

ICPC

옥상정원 반례를 못찾겠습니다ㅠ

kih629 4년 전 0

stature_lee 3년 전 2

kih629 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말