[백준] 6198 옥상정원꾸미기 (C++)

링크: https://www.acmicpc.net/problem/6198

문제

도시에는 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이다.

---

풀이

문제에서는 관리인마다 확인할 수 있는 빌딩의 옥상 수를 각각 구하여 더하였는데, 그렇게 생각한다면 쉽지 않은 문제이다.

핵심은 빌딩마다 '이 빌딩의 옥상을 확인할 수 있는 관리인의 수'를 각각 구하여 더하는 것이다.

그렇게 한다면 스택을 활용하여 다음 과정을 통해  위 문제를 풀 수 있다.

 

1. 빌딩의 높이를 입력받는다.

2. 스택이 비거나, 스택의 첫 번째 원소가 입력받은 빌딩의 높이보다 클 때까지 스택은 지운다.

3. 정답에 스택의 크기를 더한다.

4. 모든 빌딩의 높이에 대하여 1~3을 반복한다.

 

문제에 소개되어있는 예제의 경우 다음과 같다.

 

 

Stack: ( ) → (10)

먼저 1번 빌딩의 옥상을 확인할 수 있는 관리인은 당연히 아무도 없다.

빌딩의 높이를 저장하는 스택에 1번 빌딩의 높이 10을 추가한다.

 

 

Stack: (10) → (10, 3)

스택에 들어있는 이전 빌딩의 높이는 10이므로 현재 스택에 있는 빌딩들은 모두 2번 빌딩의 옥상을 확인할 수 있다.

스택에는 10 1개만이 들어있으므로, 1명이 2번 빌딩의 옥상을 확인할 수 있다.

스택에 2번 빌딩의 높이 3를 추가한다.

 

 

Stack: (10, 3) → (10) → (10, 7)

스택에 들어있는 이전 빌딩의 높이는 3이므로 현재 빌딩의 옥상을 확인할 수 없다.

또한 이전 빌딩은 현재 빌딩에 막혀 앞으로 있을 모든 빌딩의 옥상을 확인할 수 없을 것이다.

따라서 3(스택의 첫 번째 원소)을 제거해준다.

 

이어서 스택에 들어있는 이전 빌딩의 높이는 10이므로 현재 빌딩의 옥상을 확인할 수 있다.

따라서 스택에 들어있는 모든 빌딩들은 현재 빌딩의 옥상을 확인할 수 있고 이는 1이다.

스택에 3번 빌딩의 높이 3을 추가한다.

 

 

Stack: (10, 7) → (10, 7, 4)

스택에 들어있는 이전 빌딩의 높이는 7이므로 현재 빌딩의 옥상을 확인할 수 있다.

따라서 스택에 들어있는 모든 빌딩은 현재 빌딩의 옥상을 확인할 수 있고 이는 2이다.

스택에 4번 빌딩의 높이인 4를 추가해준다.

 

 

Stack: (10, 7, 4) → (10, 7) → (10) → ( ) → (12)

스택에 들어있는 이전 빌딩의 높이는 4이므로 현재 빌딩의 옥상을 확인할 수 없다.

4를 스택에서 제거한 뒤 다음 빌딩의 높이는 7이므로 현재 빌딩의 옥상을 확인할 수 없다.

7을 스택에서 제거한 뒤 다음 빌딩의 높이는 10이므로 현재 빌딩의 옥상을 확인할 수 없다.

10을 스택에서 제거하면 스택은 비게 되고 현재 빌딩의 옥상을 확인할 수 있는 관리인은 아무도 없다.

스택에 5번 빌딩의 높이인 12를 추가해준다.

 

 

Stack: (12) → (12, 2)

스택에 들어있는 이전 빌딩의 높이는 12이므로 현재 빌딩의 옥상을 확인할 수 있다.

따라서 스택에 들어있는 모든 빌딩은 현재 빌딩의 옥상을 확인할 수 있고 이는 1이다.

스택에 6번 빌딩의 높이인 2를 추가해준다.

 

위와 같이 각 빌딩마다 옥상을 확인할 수 있는 관리인의 수를 구할 수 있다.

위 예제의 경우 각각 0, 1, 1, 2, 1, 0명이고 그 합은 5이다.

 

유의할 점으로 빌딩은 총 80,000개가 존재하고 빌딩의 높이가 내림차순으로 되어있는 경우에

정답은 0+1+2+...79,999 = 3,199,960,000으로 int의 범위를 초과한다.

따라서 unsigned int 또는 long long 등의 자료형을 사용하도록 하자.

코드

#include <iostream>
#include <stack>
using namespace std;

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

    int n;
    cin >> n;

    stack<int> buildings;
    unsigned int answer = 0;

    for (int i = 0; i < n; i++){
        int height;
        cin >> height;

        while (!buildings.empty() && buildings.top() <= height){
            buildings.pop();
        }
        answer += buildings.size();
        buildings.push(height);
    }

    cout << answer;
}