[백준] 6198 옥상 정원 꾸미기

6198번: 옥상 정원 꾸미기

 

www.acmicpc.net

2493 탑과 비슷하게 풀면 된다고 생각했다가 결국 다른 방법으로 풀게 된 문제이다. 스택에 대한 많은 문제를 풀어봐야겠다고 다시 한번 느낀 문제...

풀이

순차적으로 빌딩의 높이 tmp를 입력을 받으며 stack의 데이터를 tmp를 시작으로 내림차순으로 유지하면서 현재 빌딩의 개수를 제외한 값인 stack.size() - 1을 더해주는 것을 반복하면 답을 구할 수 있다.

stack을 내림차순으로 유지하는 방법은 Monothone Stack을 참고하자.

코드

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

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

    int n;
    long long sum = 0;
    cin >> n;
    stack<int> s;

    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        while (!s.empty() && s.top() <= tmp) s.pop();
        s.push(tmp);
        sum += s.size() - 1;
    }
    cout << sum << '\n';
    return 0;
}