백준 6198 옥상 정원 꾸미기 - C++ 스택

6198 : www.acmicpc.net/problem/6198

#include <iostream>
#include <stack>
using namespace std;

stack<long long> s;
long long temp, res;
int n;

int main(){
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%lld", &temp);
        while (!s.empty() && s.top() <= temp){
            s.pop();
        }
        s.push(temp);
        res += s.size() -1;
    }
    printf("%lld\n", res);
}

---

 너비 우선 탐색 문제를 찾다가 발견한 스택 문제. 이전에 본 히스토그램 문제와 비슷한 것 같아 풀게 되었습니다. 처음에는 벡터를 사용했는데 생각해보니 temp 변수 하나만 있으면 되는거라 벡터는 바로 지웠습니다.

 

  스택에 들어가는건 현재 빌딩이며 스택의 사이즈로 이 빌딩이 볼 수 있는 건물들을 측정하게 됩니다. 

 

   - res += s.size() -1의 경우 문제의 예시로 보자면 (10 3 7 4 12 2)

 

  1. 처음 들어온 건물 외 다른 건물이 없으니 1-1 = 0     (스택 : 10)

  2. 2번째 건물이 s.top() > temp이므로 push만. 따라서 2-1 = 1 추가    (스택 : 10, 3)

  3. 들어오는 건물이 7이므로 s.top() == 3 이라 s.pop(), 따라서 2-1 = 1 추가    (스택 : 10, 7)

  4. 이번 건물은 4로 s.top() == 7이니 2번과 같은 로직, 2 추가    (스택 : 10, 7, 4)

  5. 12도 s.top보다 크니 전부 pop, 0 추가    (스택 : 12)

  6. 마지막 건물은 2가 들어오게 되니 스택에 그냥 추가, 1추가   (스택 : 12, 2)

 

 이 과정을 거치면 res에는 5가 들어가게 됩니다. 한마디로 스택의 사이즈를 더하는건 지금 있는 건물들에서 벤치마킹 할 수 있는 경우의 수가 되게 됩니다. 큰 건물이 들어오면 벤치마킹할 수 없으니 스택에서 pop을 하는 것이죠.