[C++/백준] 6198번: 옥상 정원 꾸미기

문제 링크

6198번: 옥상 정원 꾸미기

 

풀이

스택 응용 문제.. 어렵다
sum을 구할 때 int로 하면 틀린다. long long으로 해줘야 함

1. 입력값을 거꾸로 스택에 넣어주기 시작한다.
2. 현재 값을 stk의 top과 비교해서 작으면 pop하고 second를 더해준다
   1. 여기서 second는 현재 값을 포함한 지운 수가 된다.
   2. tmp에는 현재 값에서 볼 수 있는 옥상의 수가 된다.
3. 현재 값을 stk에 push한다. second는 현재 값을 포함해야 하므로 지운값+1(tmp+1)이 된다.
4. cnt에 tmp를 더한 뒤 출력한다.

 

코드

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    stack<pair<int, int>> stk;
    stk.push({ 1000000001, 1 });

    long long cnt = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        int tmp = 0;
        while (stk.top().first < arr[i])
        {
            tmp += stk.top().second;
            stk.pop();
        }
        stk.push({arr[i], tmp+1});
        cnt += tmp;
    }
    cout << cnt;
}