[백준] 6198번 - 옥상 정원 꾸미기

 

1. 문제 이해

N개의 빌딩 높이가 주어졌을 때, 각 빌딩에서 볼 수 있는 다른 빌딩의 옥상의 수를 구하는 문제이다.

다른 빌딩의 옥상을 보기 위해서는, 현재 빌딩의 높이보다 낮아야 한다. 그리고, 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 옥상은 보지 못한다.

 

이 때, 보는 방향은 오른쪽이다.

---

2. 문제 풀이

주어진 N의 범위가 (1 ≤ N ≤ 80,000) 이므로, O(N^2) 만큼 걸리는 완전탐색은 시간초과이다.

그러므로, 최대한 선형시간 내에 알고리즘이 동작하도록 만들어야 한다.

 

보는 방향이 오른쪽이므로, 가장 오른쪽에 있는 빌딩부터 진행한다. 오른쪽에서 왼쪽으로 탐색하다 보면, 다시 오른쪽으로 갈 일은 없기 때문에 선형시간이 보장된다.

 

6
10
3
7
4
12
2

 

예제 입력을 가지고 예시를 들어보자.

 

만약 7층 빌딩에서 오른쪽을 바라보면 12층 빌딩에 의해 가로막힐 것이다.

만약 3층 빌딩에서 오른쪽을 바라보면 7층 빌딩에 의해 가로막힐 것이다.

 

위와 같은 예제를 이용해 스택에 빌딩 높이를 넣어주되, Top을 가장 낮은 층으로 해서 오름차순을 가지게 만든다.

12층 빌딩 오른쪽에 7층 빌딩이 있다 한들, 12층 빌딩 왼쪽 기준에서는 아무런 의미를 가지지 못하기 때문이다.그래서 오름차순으로 만든다.

 

가장 오른쪽빌딩부터 보자.

• 2층 : 항상 0임이 보장된다. 스택에 넣어준다. Stack ( 2 )
• 12층 : 스택의 Top( 2층 ) 보다 높다. 그러므로 2층을 빼주고 12층을 넣어준다. 볼 수 있는 옥상은 2층 빌딩 하나이다   Stack (12)
• 4층:  스택의 Top(12층) 보다 낮다. 스택에 4층을 넣어준다, 그러므로 볼 수 있는 옥상이 없다. Stack (4, 12)
• 7층 : 스택의 Top(4층) 보다 높다. 오름차순 조건 만족할 때 까지 Pop 해주고 7층을 넣는다. 7층에서는 4층 빌딩의 옥상을 볼 수 있다. Stack(7, 12)
• 3층 : 스택의 Top(7층) 보다 낮으므로 3층을 넣어준다. Stack(3, 7, 12)
• 10층 : 스택의 Top(3층) 보다 높으므로,  낮아질 때 까지 Pop 해주고 10층 넣어준다. Stack(10, 12)

12층에서 2층 하나 볼 수 있으므로, Pop 한 횟수가 볼 수 있는 옥상의 수이다.

7층에서 4층 하나 볼 수 있으므로, Pop 한 횟수가 볼 수 있는 옥상의 수이다,

 

그러나, 10층에서는 3, 7,4 볼 수 있지만, Pop은 1번 해주었다. 생각해보면 3층에서 볼 수 있는 옥상은 10층에서도 무조건 볼 수 있다. 그러므로, Pop 은 3, 7 총 2번 했고, 그 횟수에 3층에서 볼 수있는 옥상의 수와 7층에서 볼 수 있는 옥상의 수를 더해준다.

 

즉, 10층에서는 3층 볼 수 있고, 3층에서는 볼 수 있는 빌딩 옥상이 없다, 볼 수 있는 옥상의 수 = 1

10층에서는 7층 볼 수 있고 7층에서는 4층을 볼 수 있다. 볼 수 있는 옥상의 수 = 1 (3층)+ 1(7층) + 1(4층)

 

즉, 오른쪽에서 왼쪽으로 가면서 각 빌딩에서 볼 수 있는 옥상의 수를 저장하는 것이다. 그러면, 오름차순을 만족하는 스택에서 정답을 구할 수 있다.

---

3. 제출 결과

---

4. 문제 코드

#include <bits/stdc++.h>
#define MAX_N 80001
using namespace std;
int building[MAX_N];
int right_small[MAX_N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> building[i];
    }
    long long sum = 0;    
    stack<pair<int,int>> st;
    st.push({building[n-1], n-1});
    for(int i=n-2; i>=0; i--) {
        int height = building[i];
        int cnt = 0;

        while(!st.empty() && height > st.top().first) {
            cnt += right_small[st.top().second];
            cnt++;
            st.pop();
        }

        st.push({height, i});
        right_small[i] = cnt;
        sum += cnt;
    }
    cout << sum;
}