3015번 오아시스 재결합 - C++

[문제]
https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

[풀이]
스택에 넣을때 순감소 수열(Ex 10 9 8 ..)이 되도록 넣어야 한다.
중복 되는 경우(Ex 2 2 2)를 고려해야 한다.

1. 스택의 top()보다 지금 값이 큰 경우
순감소 수열이 되어야 하므로, 스택의 second 값인 중복 누적 값을 더하고, top()을 pop 한다.

2. 스택의 top()보다 지금 값이 같은 경우
순감소 수열이 되어야 하므로, 스택의 second 값인 중복 누적 값을 더하고, 변수 nu에 중복 누적 값+1을 해준다.
3. 스택의 top()보다 지금 값이 작은 경우
순감소 수열을 만족하므로, 스택에 넣어주면 된다.

위 조건에 상관없이 스택에 변수가 남아있는 경우, ans+=1(맞닿아 있는 경우)를 해주면 된다.

[코드]

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    long long ans = 0;
    cin >> n;
    stack<pair<int, int>> S;
    
    while(n--){
        int t;
        cin >> t;
        int nu = 1;
        while(!S.empty() && S.top().first<=t){
            if(S.top().first == t){
                ans += S.top().second;
                nu = S.top().second+1;
                S.pop();
            }
            else {
                ans += S.top().second;
                S.pop(); nu = 1;
            }
        }
        if(!S.empty()) {
            ans++;
        }
        S.push({t, nu});
    }
    cout << ans;
}