백준 3015번 오아시스 재결합 ( C++ )

문제

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

 

해설

키의 범위가 넓어 longlong을 사용해야 하는 문제

조금 까다롭지만 길이 제한이 생긴 괄호 문제로 생각하고 풀면 풀 수 있음

 

코드

#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;
int n, cnt;
stack<pair<long long, int>> s;
long long hight;
long long ret;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> hight;
    cnt = 1;
    while (true)
    {
      if (s.empty())
      {
        s.push({hight, cnt});
        break;
      }
      else if (s.top().first < hight)
      {
        ret += s.top().second;
        s.pop();
      }
      else if (s.top().first == hight)
      {
        ret += s.top().second;
        cnt += s.top().second;
        s.pop();
      }
      else
      {
        ret++;
        s.push({hight, cnt});
        break;
      }
    }
  }
  cout << ret;
  return 0;
}