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

 

옥상 정원 꾸미기

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이다.

문제 접근

탑(백준_2493)과 유사한 유형의 문제이다.
stack을 활용하여 풀이를 시도했다.

왜 stack을 사용했는가?

가장 높은 건물 이후의 요소들은 무시되기 때문이라고 생각한다.

반복문을 사용하여 풀면 무시되는 요소들을 비교하며 진행해야 하기 때문에 시간 복잡도가 증가할 것이다.

stack을 사용할 시 높은 건물에 의한 무시되는 요소를 비교에서 제거할 수 있기 때문에 연산의 개수를 줄일 수 있다.

+ 바킹독님의 stack 문제집의 문제를 통해 접한 문제이기 때문에 왜 스택을 사용하는가를 고민한 결과다..

만약 사전 정보 없이 어떤 자료구조를 사용하는 것이 적절한가에 대한 대답은 비슷한 유형의 문제를 많이 풀어보며 체화하는 수밖에 없다고 생각한다.

예제 이해

1. 오른쪽에 해당하는 건물을 바라보고 있다.

2. 임의의 인덱스가 볼 수 있는 건물의 개수는 자신보다 높은 건물을 만나기 전 까지 증가한다.

코드

#define MAX_VAL 80001
int nums[MAX_VAL];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, count = 0;
    long long sum = 0; // sum의 범위는 21억이 넘을 수도 있다.
    stack<pair<int, long long> > S;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> nums[i];
    // 거꾸로 살펴본다.
    for (int i = n - 1; i >= 0; --i) {
        count = 0;
        // top의 높이가 현재 높이보다 높으면 해당 건물을 볼 수 있으므로 pair의 second를 늘려준다.
        while (!S.empty() && S.top().first < nums[i]) {
            // 비교하는 건물보다 낮은 건물들은 모두 볼 수 있으므로 count를 pair에 삽입해준다.
            count += S.top().second + 1;
            S.pop();
        }
        //
        S.push({nums[i], count});
        // 현재 건물에 대한 count를 총 합계에 더해준다.
        sum += count;
    }
    cout << sum;
    return 0;
}

 

※ 질문과 댓글 환영합니다 :)