백준: Class 6 - 3015

</br> 클래스 6 계속
</br>

3015: 오아시스 재결합

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

#include <bits/stdc++.h>

using namespace std;

int nums[500001];
stack< pair<int, int> > st;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    long long ans = 0;
    for(int i = 0; i < n; i++){
        pair<int, int> p = {nums[i], 1};
        while( st.size() ){
            if( st.top().first <= nums[i] ){
                ans += st.top().second;
                if( nums[i] == st.top().first ) p.second += st.top().second;
                st.pop();
            }
            else{
                ans++;
                break;
            }
        }
        st.push(p);
    }

    cout << ans << endl;

}

어렵다 풀이를 봐 버렸다
스택에 (키, 같은 키 수)로 저장해서, 만약 스택의 키보다 현재 키가 같거나 크면 스택의 같은 키 수를 답에 더한다(걔네랑은 다 가능하기 때문에). 그리고 스택의 키와 현재 키가 같다면 같은 키를 추가해 줘야 하니까 카운트를 그 만큼 늘린다.
만약 스택의 키가 현재 키보다 크다면, 그 쌍만 가능하므로 답에 하나를 추가하고 멈춘다.

ex)
6
6 6 6 5 2 5

6 6
6 6 6
6 6
6 5
5 2
5 2 5
2 5
6 5 2 5
로 답은 8임


[6] 6 6 5 2 5
stack: (6, 1)

6 [6] 6 5 2 5
stack: 
    6 <= 6
    ans += 1    {6 6}
    6 == 6이므로 카운트 +1
stack: (6, 2)
ans = 1

6 6 [6] 5 2 5
stack: 
    6 <= 6
    ans += 2    {6 6} {6 6 6}
    6 == 6이므로 카운트 +1
stack: (6, 3)
ans = 3

6 6 6 [5] 2 5
stack: (6, 3) 
    6 > 5
    ans += 1    {6 5}
    break
stack: (6, 3) (5, 1)
ans = 4

6 6 6 5 [2] 5
stack: (6, 3) (5, 1)
    5 > 2
    ans += 1    {5 2}
    break
stack: (6, 3) (5, 1) (2, 1)
ans = 5

6 6 6 5 2 [5]
stack: (6, 3) (5, 1) (2, 1)
    2 <= 5
    ans += 1    {2 5}
    2 != 5
ans = 6

stack: (6, 3) (5, 1)
    5 <= 5
    ans += 1    {5 2 5}
    5 == 5이므로 카운트 +1
ans = 7

stack: (6, 3) 
    6 > 5
    ans += 1    {6 5 2 5}
    break
stack: (6, 3) (5, 2)
ans = 8

</br>

---

정말 열심히 하자
</br>