백준 3015번 오아시스 재결합

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

 

아이디어:

1. 스택의 내림차순 유지

2. 같은 키에 대한 처리가 핵심

3. 스택에 들어가는 값은 { tmp, cnt } 로 cnt는 "스택 내에서 같은 키를 가진 사람 수"

4. 같은 키 n명에 대해 등차수열의 합 n*(n+1)/2 생각해보면 정답 변수 ans는 int형이 아닌 long long형으로 정의해야한다.

 

추가 예제:

7 2 4 1 2 2 5 1 (정답: 10)

5 5 5 2 2 5 (정답: 8)

 

스택에 내림차순 적용하는 방식은 똑같다.

cnt는 기본 1이다.

내림차순 유지를 위해 pop()을 할 때, (tmp <= S.top().first)

정답 ans에 top()의 cnt (키 같은 사람 수)를 더해준다.

만약 새로 들어온 수와 top()의 키가 같다면 cnt는 그만큼 더해준다.

 

스택에 수가 있다면 top()과 tmp는 서로 볼 수 있으므로

스택이 비어있지 않을 때 ans++

스택이 내림차순이므로 스택 내부의 top()보다 큰 요소들은 볼 필요가 없다.

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    int n, tmp;
    stack<pair<int, int>> S;
    long long ans = 0;
    cin >> n;

    while (n--) {

        cin >> tmp;

        int cnt = 1;
        
        while (!S.empty() && S.top().first <= tmp) {
            ans += S.top().second;
            if (S.top().first == tmp) cnt += S.top().second;
            S.pop();
        }
        
        if (!S.empty()) ans++;
        
        S.push({ tmp, cnt });

    }
    cout << ans;

	return 0;

}