[백준/C++] 합집합 (No. 14411)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 잘 생각해보면 정렬로 쉽게 풀 수 있다. 

 

x와 y로 사각형의 크기가 주어지기 때문에 x축과 y축의 길이를 기준으로 내림차순으로 정렬하면 가장 x축이 긴 사각형이 나온다.

 

그리고 만약 x축의 길이가 같다면 y축의 길이가 가장 큰 사각형이 나온다.

 

이때, 중요한 점은 x축의 길이를 기준으로 정렬했으므로 y축의 길이가 A인 사각형이 나오면 그 뒤에 나오는 사각형의 y축이 A보다 짧은 경우는 고려하지 않아도 된다는 점이다.

 

아래 그림을 통해 쉽게 생각해보자

fig1

 

 

위 그림에서 빨간색 사각형은 파란색 사각형보다 y축과 x축이 짧으므로 고려할 필요가 없게 된다.

 

하지만 x축이 짧아도 y축이 파란색 사각형보다 긴 초록색 사각형을 고려를 해야한다.

 

이제 이를 이용해 문제를 풀면 이전 사각형의 (x축 길이와 현재 사각형의 x축길이의 차이)*이전에 나온 사각형의 최대 y축 길이를 더해가면 사각형들의 면적의 합집합을 계산할 수 있음을 알 수 있다.

 

그러므로 x축, y축 길이를 기준으로 내림차순 정렬 후 누적해서 y축의 길이를 max로 갱신하고, x축 길이의 차를 곱해가며 면적을 계산하면 문제를 풀 수 있다.

 

+ 추가로 y축 길이가 더 높은 사각형이 나올 때만 계산하도록 하면 약간의 계산을 줄일 수 있다. 

 

 

[아이디어 정리]

1. x축과 y축 길이를 기준으로 내림차순 정렬을 한다.
2. 이전 사각형의 x축 길이와 현재 사각형의 x축 길이를 뺀다.
3. 이전에 나온 사각형들 중 최대 y길이를 계산한 다음 곱한다.
4. 최종적으로 사각형들의 합집합의 넓이를 계산해 출력한다.

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N; 
	cin >> N;
	long long x, y;
	vector<pair<long long, long long>> vp(N);
	for (int i=0; i<N; i++)
	{
		cin >> x >> y;
		vp[i] = { x,y };
	}
	sort(vp.begin(), vp.end(), [](pair<int,int> a, pair<int,int>b) {
		return a.first == b.first ? a.second > b.second:a.first > b.first;
		});

	long long maxy;
	long long prevx;
	long long ans = 0;

	// prevx==x, maxy ==y
	prevx = vp[0].first, maxy = vp[0].second;
	for (int i=1; i<vp.size(); i++)
	{
		if (maxy<vp[i].second)
		{
			ans += maxy * (prevx - vp[i].first);
			prevx = vp[i].first, maxy = vp[i].second;
		}

	}
	ans += maxy * (prevx - 0);
	cout << ans << endl;

	return 0;
}

 

 

---

 

막상 비교해보니 비교하는 부분의 계산을 줄여도 sort 하는 부분의 시간복잡도가 O(n*log n) 기 때문에 속도는 차이가 나지 않았다.

 

아이디어만 잘 생각하면 쉽게 풀 수 있는 문제였다.

 

 

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