[G5] 백준 6198번 옥상 정원 꾸미기 C++ 스택

리뷰

 

ans의 타입은 long long을 써야한다!!!!!!!!!!!

https://www.acmicpc.net/problem/6198

 

전역 변수

• n, ans : 옥상의 개수 정보를 저장할 변수 n, 정답을 저장할 변수 ans, ans는 long long타입이어야 한다!!!!
• lst : 옥상 높이 정보를 저장할 정수형 배열, 8만보다 크게 설정해 주면 된다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 lst배열에 옥상의 높이 정보를 입력 받아준다.
2. 스택으로 사용할 정수형 벡터 s를 초기화 해준다, 벡터 말고 스택으로 사용해도 무방하다.
3. 현재 스택이 비지 않았고, 스택의 맨위 인자가 현재 옥상 높이보다 작으면 스택 맨위를 pop해준다.
4. 스택의 사이즈 만큼 ans에 더해주고, 스택에 현재 옥상 높이를 추가해 준다.
5. 반복문이 완료된 후에 ans에 저장된 값을 출력해 준다.

 

참고 사항

ans의 타입은 long long을 써야한다!!!!!!!!!!!

 

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;
long long ans;
int lst[80001], n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> lst[i];
	vector<int> s;
	for (int i = 1; i <= n; i++) {
		while (!s.empty() && s.back() <= lst[i]) s.pop_back();
		ans += s.size();
		s.push_back(lst[i]);
	}
	cout << ans;
}