[알고리즘] 백준 6198 옥상정원꾸미기 // 스택, 역발상, 자기중심적 사고, st.size() 도 의미가 있다.

* 풀이

• 유사문제들의 풀이의 공통점
  • 계산이 끝난 원소를 바로 while문으로 pop 하는 특징
  • (top <= current) -> 나보다 작은 top -> 나를 볼수없음 -> pop 
  • 남은 스택의 원소갯수 = 나를 볼수있는 빌딩의 갯수!
• 예시 낚시
  • 예시는 관리인 시점에서 탐색중인 current가 아니라 탐색이 끝난 element 관점으로 서술되어있다.
  • 이러면, 상태관리가 어려워진다.
  • 문제 해결에서 "현재 위치(current)"를 중심으로 생각하는 것은 매우 좋은 접근 방법
    
    이런 관점이 유용한 이유는:
    
    1. 문제를 더 작은 단위로 나눌 수 있음
       - "전체 빌딩이 몇 개를 볼 수 있는가?" 대신
       - "현재 빌딩(나)에 대해서는 어떤 일이 일어나는가?"
    
    2. 상태 관리가 쉬워짐
       - 현재 시점에서 필요한 정보만 유지
       - 이 문제에서는 스택에 현재보다 높은 빌딩만 남김
    
    3. 반복되는 패턴을 찾기 쉬움
       - 각 위치에서 동일한 로직 적용
       - 이 문제에서는 "나보다 작은 빌딩 제거" -> "스택 크기 확인" -> "나를 스택에 추가"
    
    비슷한 예시들:
    ```
    - 투 포인터: 현재 위치의 포인터를 기준으로 판단
    - DFS/BFS: 현재 노드에서 할 수 있는 행동 결정
    - DP: 현재 상태에서의 최적해 계산
    ```
    
    이렇게 "현재"를 중심으로 생각하면 복잡한 문제도 단순한 단위로 나누어 해결가능

나를 볼수있는 빌딩이 몇개인지 세는 문제로 바꿔야한다.

* 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n;
vector<ll> arr;
stack<pair<ll,ll>> s;
ll ret;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n ;

    for (int i = 0; i < n; ++i) {
        ll tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }

    s.push({0,arr[0]});
    for (int i = 1; i < n; ++i) {
        // 현재 빌딩보다 작거나 같은 빌딩은 나를 볼수 없으므로 제거
        while(s.size() && s.top().second <= arr[i]) {
            s.pop();
        }
        // 스택에 남아있는 빌딩의 수가 현재 빌딩을 볼 수 있는 빌딩의 수
        // 나보다 작은 빌딩은 위에서 다 제거했음.
        ret+=s.size();

        // 현재 빌딩 정보를 스택에 추가
        s.push({i, arr[i]});
    }
    
    cout<<ret;
    
    return 0;
}