[c/c++] BOJ 6198번 문제 - 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

문제

문제풀이

#include <bits/stdc++.h>
using namespace std;

//옥상 정원 꾸미기
//2493 탑의 반대문제이라고 생각됨.
//O(n)
//스택의 사이즈를 더하는건 지금 있는 건물들에서 벤치마킹 할 수 있는 경우의 수가 되게 함.
//이를 반대로 생각해보면, 1번은 아무도 볼 수 없고, 2번은 1번에서만 볼 수 있다. 또한 3번은 1번에서만 볼 수 있고, 4번은 1, 3번에서만 볼 수 있다.
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    stack<long long> st;
    long long ans=0;
    for(int i=0;i<n;i++){
        long long num;
        cin >> num;
        while(!st.empty()){
            if(st.top() <= num){
                st.pop();
            }else{
                break;
            }
        }
        st.push(num);
        ans+=st.size()-1;
    } 
    cout << ans;
    return 0;
}

문제의 포인트

• 2493번 문제와 매우 유사
• 스택의 사이즈를 더하는 이유는 지금 있는 건물들에서 벤치마킹할 수 있는 경우의 수가 되게 함.
• 반대로 생각해보기.