본문 바로가기
PS/BOJ

[백준] 6198. 옥상 정원 꾸미기(c++)

by backend 개발자 지망생 2025. 2. 3.

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;
}