백준 6198 옥상 정원 꾸미기 (C++)

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

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    long long ans = 0;
    cin >> n;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    stack<int> st;

    for (int i = 0; i < n; i++) {

        while (!st.empty() && st.top() <= arr[i]) {
            st.pop();
        }

        ans += st.size();
        st.push(arr[i]);

    }

    cout << ans;

    return 0;
}

1. 문제

n(1<=n<=80,000)개의 건물의 옥상의 높이 (1 ≤ h ≤ 1,000,000,000) 가 주어진다. 각 건물의 관리인은 건물의 옥상으로부터 우측에 있는 건물의 옥상을 확인하는 데, 본인이 담당한 건물보다 낮은 높이의 건물만 확인할 수 있다. 이 때, 모든 관리인이 확인할 수 있는 옥상의 수의 합을 구하라.

2. 풀이

스택에는 현재 건물을 확인할 수 있는 건물이 들어가게 된다. 하나씩 들여다보자.

우선 첫 건물을 스택에 넣어준다.

그 다음 건물이 들어올 때, 스택의 top에 있는 건물 중 현재 건물 이하 높이의 건물은 현재 건물을 확인할 수 없으므로 빼준다.

높이가 7인 건물을 넣을 때, 높이가 3인 2번 건물에서는 현재 건물을 확인할 수 없으므로 스택에서 pop한다. 그러면 스택에는 3번 건물의 옥상을 확인할 수 있는 1번 건물만 남게 된다. 이 개수를 더해준다. 이를 반복하여 문제를 풀 수 있다.

    long long ans=0;
    for (int i = 0; i < n; i++) {

        while (!st.empty() && st.top() <= arr[i]) {
            st.pop();
        }

        ans += st.size();
        st.push(arr[i]);

    }

    cout << ans;

위 로직을 구현하면 위와 같다. 단, 건물의 개수가 8만개에 각 높이가 10억 이하이므로 long long으로 선언해준다. 연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.