백준 6198 옥상정원꾸미기 c++ ver.2

이것도 전에 풀었으나 다시 새로푼다. 좀더 간결하고 생각 잘해서 지저분하지 않게..

 

왼쪽부타 각각의 건물이 존재한다.

각각의 건물이 몇개를 볼 수 있는지를 카운팅 하는것도 좋다.

 

하지만 왼쪽부터 스택에 넣으면서 몇개의 건물이 방금 스택에 넣은 건물을 볼 수 있는지를 보면 간결해진다.

 

맨 왼쪽에 탑을 일단 스택에 넣는다.

두번째 탑을 넣기 전에, 

두번째 탑이 첫번째 탑보다 같거나 크면 첫번째 탑을 스택에서 삭제시켜준다.

사실 예를들어서 첫번째탑을 삭제하는거지 그냥 자기보다 작은게있으면 싹다 지워준다.

그리고 푸시하기 직전 스택에 쌓여있는 개수를 카운트하고 푸시한다.

 

 

#include <bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    int n;

    cin >> n;

    stack<long long int> s;

    long long int total = 0;

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

        long long int temp;

        cin >> temp;

        while(!s.empty() && s.top() <= temp){

            s.pop();

        }

        total += s.size();

        s.push(temp);

    }

    cout << total;

}

 

왕간단.