[Algorithm] Baekjoon 6198번 : 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

struct Node
{
    int num;
    int index;
};
 
vector<Node> v;
stack<Node> monotonicStack;
vector<int> indexArr;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, input;
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
 
        v.push_back({ input,i });
    }
 
 
    for (int i = v.size() - 1; i >= 0; --i)
    {
        Node cur = v[i];
 
        if (monotonicStack.empty())
        {
            monotonicStack.push(cur);
            indexArr.push_back(i);
        }
        else
        {
            while (!monotonicStack.empty() && monotonicStack.top().num < cur.num)
            {
                monotonicStack.pop();
            }
 
            if (monotonicStack.empty())
            {
                monotonicStack.push(cur);
                indexArr.push_back(i);
            }
            else
            {
                indexArr.push_back(monotonicStack.top().index);
                monotonicStack.push(cur);
            }
        }
    }
 
    reverse(indexArr.begin(), indexArr.end());
 
    long long answer = 0;
 
    for (int i = 0; i < indexArr.size(); ++i)
    {
        long long num = (long long)indexArr[i] - i - 1;
        if (num < 0)
        {
            num = indexArr.size() - 1 - i;
        }
        answer += num;
    }
 
    cout << answer;
}

 

쉽게 풀 줄 알았는데 monotonic stack 이라는 개념을 배워야 쉽게 풀 수 있는 문제.

상당히 유용하다고 생각되기에, 꼭 알았으면 좋겠고 쉽게 이해할 수 있는 글로는 아래링크를 남긴다.

https://iridescentboy.tistory.com/146

Monotonic Stack, 단조 스택이란?

 

다만 이 문제에서는 자기 높이 '이상'의 건물들이 있을 경우 이후를 못본다고 되어있다는것을 알아야 한다.

즉, 모노토닉스택에서의 형태가 내림차순이긴한데 같은값도 포함시켜 주는 형태가 되어야 한다.

 

이 문제에서의 포인트는 자신 이후에 처음 만나는 자기 높이 '이상'의 건물이 몇번째에 위치해있는가? 가 중요하다.

그렇기 때문에 모노토닉스택에서의 내림차순 또한 값이 같을 경우도 push해주는 형태가 되어야하기에 위 코드의 40번째 줄에서 pop해주는 조건으로 <=이 아닌 <을 한 것이다.

즉, 모노토닉 스택에 같은값이 있는것도 허용해주는 것을 표현했다고 볼 수 있다.

 

 

 

===========================================================================================

 

사실 저렇게 어려운 개념을 생각하면서 풀 필요가 없었다.

굳이 왜 저렇게까지했는지 ;; 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
int n, num;
vector<int> v;
stack<int> s;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    
    unsigned long long result = 0;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> num;
        
        while (!s.empty() && s.top() <= num)
        {
            s.pop();
        }
 
        result += s.size();
        s.push(num);
    }
 
    cout << result;
}
 

 

각 건물들이 바라보는 건물의 개수의 '총합'을 구하는 것이기 때문에, 현재 건물을 몇개의 건물이 바라볼 수 있는지를 합산해서 정답을 출력하는 코드이다.

 

즉, 스택에 현재선택된 건물보다 좌측의 큰건물들의 개수를 유지해나간다는 개념이다.