[BOJ] 옥상 정원 꾸미기 6198번 C++

 

문제

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

 

접근 방식

 

스택을 이용해서 풀이하면 되는데

왼쪽 빌딩부터 오른쪽 빌딩 순으로 반복문을 돌면서

스택에는 현재 건물보다 같거나 낮은 건물은 제거하고, 현재 볼수있는 건물만 남겨둔다

이렇게 하면 현재 건물에서 볼 수 있는 빌딩들의 수를 더해주면 끝이다

 

즉 10 3 7 4 12 2 건물이 있을 때

10은 현재 스택에 비어있으니까 볼 수 있는 건물의 수는 0

3은 현재 스택의 top 값이 10인데 3보다 크니 3을 볼 수 있는 건물이니 1

7은 현재 스택의 값 [10,3] 중 3을 제외한 10이 7을 볼 수 있는 건물이니 1

...

이런식으로 하면 전체 합이 0 + 1 + 1 + 2 + 0 + 1 = 5로 원하는 총합을 구할 수 있다.

 

코드

#include<bits/stdc++.h>
using namespace std;

int main() {
    int N; cin>>N;
    stack<int> st;
    long long cnt = 0;

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

        while(!st.empty() && st.top() <= h) {
            st.pop();
        }

        cnt += st.size();
        st.push(h);
    }
    cout<<cnt;
}