백준
[백준] 6198번 옥상 정원 꾸미기 (stack, c++)
해랑쓰
2021. 10. 5. 10:28
728x90
반응형
스택에는 현재 인덱스 i를 집어넣는다.
그 전에 스택이 비어있지 않으면 스택의 최상단(위치 prev)과 현재 높이(위치 i)의 차이 -1(자기자신은 빼줌)
개수 만큼의 빌딩을 볼 수 있다는 이야기이다.
n=80000이고 자기 위치 다음 빌딩들이 모두 자기보다 작다하면 80000+ 79999 + 79998 +... 이런 예시가 들어온다
대략 n^2으로 계산하면 6.4*10^9 으로 int 범위가 넘어가므로 ans는 long long 형으로 해준다.
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
int n;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
vector<int> v(n);
long long sum = 0;
stack<int> s;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 0; i < n; i++) {
while (!s.empty() && v[s.top()]<=v[i]) {
int prev = s.top();
s.pop();
sum+= i - prev - 1;
}
s.push(i);
}
while (!s.empty()) {
int prev = s.top();
s.pop();
sum += n - prev - 1;
}
cout << sum;
return 0;
}
728x90
반응형