백준[3015] 오아시스 재결합

문제 설명

문제 링크

http://icpc.me/3015

3015번: 오아시스 재결합

풀이

스택을 이용하여 풀 수 있다.

이 문제는 i번째 사람이 1 ~ i -1번째 사람 중에서  몇 명을 볼 수 있는지 확인하면 된다.

여기서 잘 관찰을 해보자면 i번째 사람이 볼 수 있는 사람은 자기보다 큰 사람에 막히지 않은 사람들이다.

그렇다면 사람들을 자기보다 큰 사람이 앞에 있어 볼 수 없는 사람과 볼 수 있는 가능성이 있는 사람들로 나눌 수 있다.

그럼 이제 가능성이 있는 사람들만 가지고 관찰을 하면 된다.

1 ~ n명의 사람을 순서대로 스택에 넣으면서 스택은 항상 내림차순을 유지하게 하면 가능성이 있는 사람들만으로 유지된다.

만약 스택에 4 2 1가 들어있는 상황에 3이 들어온다면 2, 1은 3에 가려지기 때문에 다음 수가 들어오면 볼 수 있는 가능성이 없어지는 것을 생각하면 된다.

그럼 이제 이 가능성이 있는 사람들을 어떻게 체크할지만 해결하면 된다.

만약 5 4 2 1에 3이 들어온다면 4, 2, 1을 볼 수 있다. 이것을 잘 관찰해보면 새로 들어오는 수는 자기보다 큰 놈을 만날 때까지 만나는 사람을 다 볼 수 있다. 그럼 1, 2를 pop 하며 볼 수 있는 사람도 늘려나가고 4를 만나면 push를 하며 볼 수 있는 사람을 늘리면 된다.

그럼 만약 4 2 1에 1이 들어오면 1을 pop 하고 볼 수 있는 사람을 늘리고, 2를 만나고 볼 수 있는 사람을 늘리면서 push를 하면 어떻게 될까? 그렇다면 stack에는 또 4 2 1이 남게 되고 여기서 또 더 작은놈이 들어온다면 원래는 마지막에 들어온 1을 두개 다 볼 수 있기 때문에 문제가 생길 것이다. 그럼 stack에 pop을 하면서 같은 놈이 몇 개 있는지 체크를 하고 다시 넣어줄 때 같은 놈의 개수만큼 넣어줘야 한다. 그렇게 구현하기 위해 pair를 사용해 second값에 동일한 수가 몇 개 들어있는지 체크를 해줬다.

코드

#include <cstdio>
#include <stack>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int arr[500005];
ll ans;
stack<pii> s;

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        while (!s.empty() && s.top().first <= arr[i]) {
            if (s.top().first == arr[i]) {
                cnt += s.top().second;
                ans += s.top().second;
                s.pop();
            } else {
                ans += s.top().second;
                s.pop();
            }
        }
        if (!s.empty()) ans++;
        s.push({arr[i], cnt});
    }
    printf("%lld", ans);
}