BOJ/백준 2304 창고 다각형

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

 

해결 아이디어

가장 높은 기둥을 기준으로 양쪽의 면적을 계산해주는 방식으로 문제를 해결 하면 될 것 같았다.

지금은 알고리즘을 복습하는 단계라서 문제 태그를 보고 또 연습을 하면서 푸느라 스택을 사용해서 풀었으나 솔직히

그냥 브루트포스로 풀어도 시간초과가 나지 않을 것 같았다.

#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, ans = 0;
    cin >> n;

    vector<pair<int, int>> v;
    stack<pair<int, int>> s, s2;

    for(int i = 0; i < n; i++){
        int l, h;
        cin >> l >> h;
        v.push_back({l, h});
    }

    sort(v.begin(), v.end(), [](pair<int, int>& a, pair<int, int>& b){
        return a.first < b.first;
    });

    for(auto tmp : v){
        if(s.empty()) s.push(tmp);
        if(!s.empty() && s.top().second <= tmp.second){
            ans += (s.top().second * abs(s.top().first - tmp.first));
            s.pop();
            s.push(tmp);
        }
    }
    
    sort(v.begin(), v.end(), [](pair<int, int>& a, pair<int, int>& b){
        return a.first > b.first;
    });

    for(auto tmp : v){
        if(s2.empty()) s2.push(tmp);
        if(!s2.empty() && s2.top().second < tmp.second){
            ans += (s2.top().second * abs(s2.top().first - tmp.first));
            s2.pop();
            s2.push(tmp);
        }
    }

    if(!s.empty() && !s2.empty() && s.top().first == s2.top().first && s.top().second == s2.top().second){
        ans += 1 * s.top().second;
    }

    cout << ans;
    return 0;
};

 

예외 처리를 해준 것이 있다면 왼쪽부터 검사할때는 <= 이지만 오른쪽 부터 검사를 시작할 때는 < 이다

왜냐하면 최고로 높은 높이의 기둥이 1개만 있다고 하지 않았기 때문에 이것을 처리 하기 위해서 조건을 처리 해줬다 그리고

    if(!s.empty() && !s2.empty() && s.top().first == s2.top().first && s.top().second == s2.top().second){
        ans += 1 * s.top().second;
    }

이 부분은 오른쪽에서도 검사 했을때 x축의 위치가 같으면 제일 높은 기둥의 면적을 추가 해주지 않은 것이니 값을 더 해준다

만약 최고로 높은 기둥이 2개 이상 있다고 가정하면 왼쪽부터 검사 할때 이미 값을 계산하고 push를 통해 2번째 기둥의 위치 값을

저장해 주기 때문이다.