3015. 오아시스 재결합

https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

 

문제 설명

N명이 한 줄로 서 있는데, i번째에 서있는 사람과 j번째에 서있는 사람 (i < j) 사이에 둘중 한 명보다 키가 큰 사람이 없으면 서로 볼 수 있다고 한다.

이 때, 서로 볼 수 있는 쌍의 수를 구하는 문제이다.

 

solution

i번째에 서있는 사람과 j번째에 서있는 사람 사이에 둘 중 한 명 보다 키가 큰 사람이 있으면 서로를 볼 수 없고,

만약 i번째에 서있는 사람보다 크다면 그 뒤에 있는 사람은 모두 볼 수 없을 것이다.

그렇다면 i번째에 서있는 사람은 더이상 쌍을 이룰 수 없다.

 

이런 상황을 고개를 90도 틀어서(?) 보면 스택이 보인다!

스택 안에는 단조증가하는 수들이 있어야 하며, 현재 줄을 서는 사람보다 작은 사람들은 스택에서 빼면서 총 쌍의 수에 더해주면 된다. (그 사람과 쌍을 이룰 수 있기 때문.)

 

이 문제에서 포인트는 키가 같은 사람인데,

키가 같은 사람은 스택에서 같이 있어야 한다. 스택에 pair<int, int> 형태로 first는 키, second는 키가 같은 사람 수 로 저장한다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for(int i=0;i<n;i++)
    {
        cin >> v[i];
    }
 
    stack<pii> st;
    st.push({v[0], 1});
    
    int ans = 0;
    for(int i=1;i<n;i++)
    {
        int num = 1;
        while(!st.empty()  && st.top().first <= v[i])
        {
            if(st.top().first == v[i])
            {
                ans += st.top().second;
                num = st.top().second+1;
                st.pop();
            }
            else
            {
                ans += st.top().second;
                st.pop();
                num = 1;
            }
        }
        if(!st.empty()) ans++;
        st.push({v[i], num});
    }
    cout << ans;
 
    return 0;
}