BOJ 6198 c++ 옥상 정원 꾸미기

BOJ 6198 c++ 옥상 정원 꾸미기

백준 6198 cpp 옥상 정원 꾸미기

나는 스택 문제가 왜 이렇게 적응이 안 되는지 모르겠다. 한참을 헤매다 결국 답을 보고 말았다.

문제의 원리는 간단하다.

1. 요소를 하나씩 배열에 넣는다.
2. for문으로 배열의 크기만큼 돈다.
3. 스택에 하나씩 넣으면서, 스택의 top보다 현재 배열의 요소가 더 크거나 같은 동안 s.pop()을 해준다.
4. 스택에 현재 배열의 요소를 push한다.
5. 결과값에 S.size() - 1 만큼을 더한다.

정답 코드 :

(80000개의 배열이 모두 내림차순인 경우 int의 범위를 벗어나므로 long long형을 선언.)

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

int ea;
stack <int> st;
int buildingArr[80005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    long long ans = 0;

    for (int i = 0; i < ea; i++) {
        while (!st.empty() && st.top() <= buildingArr[i]) {
            st.pop();
        }

        st.push(buildingArr[i]);

        ans += st.size() - 1;
    }

    cout << ans;
}

유형: 스택