문제

Code

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

using namespace std;

int arr[80005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N,max=0,input;
    long long cnt=0;
    stack<int> S;

    cin >> N;

    for(int i=0;i<N;i++)
        cin >> arr[i];

    for(int i=0;i<N;i++)
    {
        while(!S.empty() && S.top() <= arr[i])
        {
            S.pop();
        }
        S.push(arr[i]);

        cnt += S.size()-1;
    }
    cout << cnt;
}

• 풀이를 참고함;
• 스택을 사용
• cnt가 80,000 까지 내림차순 합이 될 경우 숫자가 매우 커지므로 long long을 사용해야 한다.
• S.top() > arr[i] 이 되어야 내려다볼 수 있기 때문에 cnt를 증가시킬 수 있다. 이 조건이 될 떄 까지 S.pop()
• 그리고 나서 cnt += S.size()-1 해주어야 해당 빌딩을 위에서 볼 수 있는 건물의 수를 구할 수 있음
• 나중에 다시 풀어봐야 할 듯