https://www.acmicpc.net/problem/6198
같거나 큰 빌딩이 있으면 그다음에 있는 모든 빌딩의 수를 못본다.
이번에 stk의 두번째 값에는 인덱스를 넣어서 계산 시 현재 i와 stk.top.second의 값을 계산해서 넣어주는 것이 핵심이었던 것 같다.
마지막으로 stack에 있는 값을 flush해주는 반복문까지 해주면 끝이다.
#include<iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <stack>
#include <list>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
// 입력값 받을 배열
int arr[80002];
// 정답 배열
// int answer[80002] = {0};
long long int answer = 0;
// 스택
stack<pair<int, int> > stk;
cin >> n;
stk.push(make_pair(1087654321, 0));
for (int i = 1; i <= n; i++) {
cin >> arr[i];
while (stk.top().first <= arr[i]) {
answer += i - stk.top().second - 1;
stk.pop();
}
stk.push(make_pair(arr[i], i));
}
while (stk.top().first < 1087654321) {
answer += n - stk.top().second;
stk.pop();
}
cout << answer << " ";
return 0;
}
'PS > BOJ' 카테고리의 다른 글
[백준] 6549. 히스토그램에서 가장 큰 직사각형(c++) (0) | 2025.02.04 |
---|---|
[백준] 17298. 오큰수(c++) (0) | 2025.02.03 |
[백준] 2493. 탑(c++) (0) | 2025.02.03 |
[백준] 3015. 오아시스 재결합(c++) (0) | 2025.02.02 |
[백준] 6198. 옥상정원 꾸미기(c++) (0) | 2025.01.31 |