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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 높이가 서로 다른 빌딩이 있고 현재 빌딩보다 높이가 낮은 빌딩만 볼 수 있을 때 각 빌딩에서 볼 수 있는 빌딩의 총합을 구하면 된다.

단, 오른쪽 빌딩만 관찰할 수 있다.

 

처음에는 LCS같이 접근하면 되겠다고 생각했다.

오른쪽만 볼 수 있다는 조건과 높이를 따져야 하는 조건이 LCS처럼 최장 증가 부분 수열을 만드는 개념을 적용할 수 있을 거라 생각했다.

하지만, 이 논리에는 오류가 있는 게 최장 증가 부분 수열에 포함되지 않는 요소에서도 관찰을 해야 하기 때문에 적절하지 않다고 생각했다.

 

그다음으로 떠올린 방법이 Stack을 활용하는 것이다.

각 빌딩을 살펴보며 이전 빌딩이 현재 빌딩보다 작다면 그 빌딩은 더 이상 다음 빌딩을 관찰하지 못한다.

예를 들어,

10 3 7 4 12 2

이렇게 빌딩의 높이가 주어졌을 때, 3은 7 이후의 빌딩을 관찰하지 못한다.

10, 3, 7, 4도 마찬가지로 12 이후의 빌딩을 관찰하지 못한다.

 

즉, 현재 빌딩(i번째 빌딩)이 이전 빌딩(j번째 빌딩) 보다 크거나 같다면 그 빌딩이 볼 수 있는 한계가 i로 정해지는 것이다.

따라서, 이전 빌딩들이 볼 수 있는 건물은 i - j - 1개가 된다.

 

이를 효율적으로 적용하려면 stack이 필요하다.

이전 빌딩 중 자신보다 작거나 같은 빌딩들은 모두 한계를 정할 수 있기 때문에 stack에 있는 빌딩 중 자신보다 큰 빌딩이 나오기 전까지 반복하여 뽑아내 볼 수 있는 건물의 수를 갱신한다.

이후, 현재 빌딩을 스택에 넣는다.

이렇게 진행하면 스택은 내림차순으로 정렬된 형태를 유지하게 된다.

buildingStack.push_back({ buildings[0], 0 });
for (int i = 1; i < N; i++)
{
    while (!buildingStack.empty())
    {
        auto& [h, idx] = buildingStack.back();

        if (h > buildings[i]) break;

        buildingStack.pop_back();
        ans += i - idx - 1;
    }

    buildingStack.push_back({ buildings[i], i });
}

마지막에 stack이 남아있다면 동일한 작업을 진행해 준다.

남아있는 빌딩들은 빌딩들의 오른쪽 끝까지 볼 수 있는 빌딩들이다.

while (!buildingStack.empty())
{
    auto& [h, idx] = buildingStack.back();
    buildingStack.pop_back();

    ans += N - idx - 1;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<int> buildings;
vector<pair<int, int>> buildingStack;

int main() 
{
    INPUT_OPTIMIZE;

    cin >> N;
    buildings.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> buildings[i];
    }

    long long ans = 0;

    buildingStack.push_back({ buildings[0], 0 });
    for (int i = 1; i < N; i++)
    {
        while (!buildingStack.empty())
        {
            auto& [h, idx] = buildingStack.back();

            if (h > buildings[i]) break;

            buildingStack.pop_back();
            ans += i - idx - 1;
        }

        buildingStack.push_back({ buildings[i], i });
    }

    while (!buildingStack.empty())
    {
        auto& [h, idx] = buildingStack.back();
        buildingStack.pop_back();

        ans += N - idx - 1;
    }

    cout << ans;

    return 0;
}

---