[ 백준 / C++ ] 2304 : 창고 다각형

[ 문제 ]

 

2304번: 창고 다각형

 

[ 접근방법 ]

 

스택을 활용하여 값을 갱신한다.

 

일단 입력값을 위치순으로 정렬한 후, 문제 5번 조건을 위해 스택에 저장된 값과 입력값을 비교해준다.

 

"스택에 저장된 값 < 입력값" 일 때 상황에 맞게 처리를 해주면 된다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n, ans;
vector<pair<int, int>> vec;
stack<pair<int, int>> st;

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

    cin >> n;
    vec.resize(n);

    for (int i = 0; i < n; i++)
    {
        cin >> vec[i].first >> vec[i].second;
    }
    sort(vec.begin(), vec.end());

    st.push(vec[0]);
    for (int i = 1; i < n; i++)
    {
        pair<int, int> p = st.top();

        while (!st.empty() && st.top().second < vec[i].second)
        {
            p = st.top();
            st.pop();
        }

        if (st.empty())
        {
            ans += (vec[i].first - p.first) * p.second;
        }

        st.push(vec[i]);
    }

    while (!st.empty())
    {
        pair<int, int> p = st.top();
        st.pop();

        if (!st.empty())
        {
            ans += (p.first - st.top().first) * p.second;
        }
        else
        {
            ans += p.second;
        }
    }

    cout << ans;

    return 0;
}