백준 14411번 합집합

문제 링크입니다: https://www.acmicpc.net/problem/14411

얼핏 보면 라인 스위핑 문제 같지만 라인 스위핑 문제보다는 쉬운 문제였습니다.

라인 스위핑 문제인줄 알고 시도조차 안했지만 같은 학교 학우이신 Green55님(https://blog.naver.com/pasdfq/221367374753)의 설명을 듣고 풀 수 있었습니다.

알고리즘은 아래와 같습니다.

1. 좌표를 입력받은 뒤 넓이를 구할 때 필요한 좌표만을 남깁니다.

-> 좌표 (x, y)가 있을 때 다른 좌표 (a, b)에 대해 (x<=a && y<=b)라면 (a, b)에 묻혀 (x, y)는 효력이 없을 것입니다.

2. 주어진 좌표를 x축에 대해 오름차순 정렬을 합니다.

-> i < j에 대해 x[i] < x[j]는 무조건 성립

3. 2번에 의해 i < j에 대해 y[i] < y[j]가 성립한다면 i 번째 좌표는 무시해도 됨을 알 수 있습니다.

4. 1 ~ 3번에 의해 필요한 좌표만 남았으므로 이제 넓이를 구해주면 됩니다.

* pair<long long, long long> 형으로 저장하는 이유는 int형으로 저장할 경우 int형의 곱셈에 대해 overflow가 발생할 수도 있기 때문입니다!

#include <iostream>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        //넓이는 long long일 수 있으므로

        vector<pair<long long, long long>> v;

        for (int i = 0; i < N; i++)

        {

                 int x, y;

                 cin >> x >> y;

 

                 v.push_back({ x, y });

        }

        sort(v.begin(), v.end());

 

        vector<int> s; //벡터를 스택처럼

        s.push_back(0);

        //의미 있는 좌표만 남긴다

        for (int i = 1; i < N; i++)

        {

                 while (!s.empty())

                 {

                         pair<long long, long long> top = v[s.back()];

                         pair<long long, long long> cur = v[i];

                         //스택의 탑이 v[i]에 의해 무시당하는 경우

                         if (top.second < cur.second)

                                 s.pop_back();

                         else

                                 break;

                 }

                 s.push_back(i);

        }

 

        //의미 있는 좌표의 인덱스를 기반으로 넓이 구함

        long long result = v[s[0]].first * v[s[0]].second;

        for (int i = 1; i < s.size(); i++)

                 result += (v[s[i]].first - v[s[i - 1]].first)*v[s[i]].second;

 

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~