[백준] 3015 - 오아시스 재결합 (C++)

 

1. 문제 소개 

 

 

2. 생각해야 할 거 

키 같으면 볼 수 있음 

 

이런식으로 들어간다 

 

이렇게 생각하면 더 큰 '벽'을 만나기 전 광선이 어디까지 가느냐 묻는 문제라고 해도 본질적으로 같다 (상관은 없지만)

 

3. 알고리즘 활용 

monotone stack을 활용한다.

모노톤 스택은 정리가 끝난 후가 아니라 각종 operation을 반복하면서 거기서 발생하는 정보가 유의미하다. 

 

예를 들어서 이 문제에서는 stack안의 원소들을 내림차순(정확히는 non-increasing) 으로 유지하면서, pop 하기 전에 수를 카운트한다. 

 

• 작은 키는 뒤에서 더 큰 키를 만나면 영원히 가려져서 쓸모 X -> 팝(pop).
• 같은 키는 서로 다 볼 수 있음 -> 키 같은 경우 카운트하고 합쳐서 처리  
• 더 큰 키 가려지지 않아서 쓸모 있음 -> 남겨 둠 

 

4. 코드 

#include<stdio.h>
#include<iostream>
#include <stack>

using namespace std;

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

    int N;
    long long cnt = 0;
    cin >> N; 

    stack <pair<int, int>> S;

    for (int i = 0; i < N; ++i){
        int same =1;
        int h;
        cin >> h;

        while(!S.empty() && S.top().first < h){
            cnt += S.top().second;
            S.pop();
        }

        while(!S.empty() && S.top().first == h){
            cnt += S.top().second;
            same += S.top().second;
            S.pop();
        }   

        if (!S.empty()) cnt += 1;
        S.push({h, same});
    }

    cout << cnt << endl;
}