백준 6198 옥상정원꾸미기

앞선 탑 문제와 비슷한 유형의 문제이며 스택을 활용한다.
2시간 이상 붙잡고 고민했으나, 해결하지 못하고 구글링을 했다.

답은 다음과 같다.

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

#define ll long long

stack<int> s;
int N;
ll ans;

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

    cin >> N;
    ll height;
    while(N--) {
        cin >> height;
        while(!s.empty() && s.top() <= height) s.pop(); 
        ans += s.size();
        s.push(height);
    }
    cout << ans;
    return 0;
}

처음에 구현했을 때, 이전 것과 비교하여 옥상을 확인하는 횟수를 더하는 식으로 구현했는데 도저히 해결하지 못했다.

해결코드를 보니 스택의 size를 더하는 식으로 구현을 하였다.

하.. 조금만 더 생각을 해봤어야 했다..
너무 아쉬운 문제이다.

다음에는 좀 더 테스트 코드를 보며 특징을 잘 찾아내어 해결할 수 있는 방법을 폭넓게 찾아봐야겠다.