백준 2170 C++

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

 

처음엔 당연히 배열을 생각했지만 너무 범위가 넓어서 시간 복잡도가 너무 높아진다.

결국 pair sort를 해서 문제를 풀었다.

pair를 sort하면 frist가 작은거 순으로 나열되기 성질을 이용하여 문제를 풀었다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;	//선의 개수
ll result;

vector<pair<ll, ll>> v;

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

	cin >> n;

	ll x, y;
	int v_index = 0;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		v.push_back({ x, y });
	}

	//아래처럼 sort하면 first는 작은거부터 나열되서 생각할 범위가 줄어든다.
	sort(v.begin(), v.end());

	int s = v[0].first, e = v[0].second;
	for (int i = 1; i < n; i++) {
		if (v[i].first >= s && v[i].first <= e) {		//작은게 사이에 있다. -> 연장이 된다.
			if (v[i].second > e) {		//v[i]의 끝점이 현재의 끝점보다 멀다면 끝점을 갱신시켜준다.
				e = v[i].second;
			}
		}
		else {		//v[i]의 작은게 위 사이에 없다. 즉 새로운 줄이다.
			result = result + abs(s - e);		//기존에 있던 걸 result에 더해준다.

			s = v[i].first; e = v[i].second;		//새로 시작점과 끝점을 갱신한다.
		}
	}

	result = result + abs(s - e);

	cout << result;
}