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

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

 

풀이

각 높이별로 가장 왼쪽에 있는 기둥과 가장 오른쪽에 있는 기둥을 구해서 그 사이 면적을 계속 더해주는 식으로 코드를 작성하였다 

 

 

제출 코드

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

pair<int, int> arr[1001];

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

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

    sort(arr, arr + n);

    int sum = 0;
    for (int i = 1; i <= 1000; i++)
    {
        int left = 0, right = 0;
        for (int j = 0; j < n; j++)
        {
            if (arr[j].second >= i)
            {
                if (!left) left = arr[j].first;
                right = max(right, arr[j].first + 1);
            }
        }
        sum += (right - left);
    }

    cout << sum;
}

 

 

다른 풀이

가장 높은 기둥을 구하고, 왼쪽과 오른쪽에서 각각 이동하며 가장 높은 높이를 갱신해서 각 L마다 더해주는 방식으로 더 간단하게도 구현이 가능하다