[백준 2170] 선 긋기

백준 2170번 : 선 긋기

www.acmicpc.net/problem/2170

2170번: 선 긋기

---

/* 문제 설명 */

여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없을 때, 그려진 선들의 총 길이를 구하시오.

(선이 여러 번 그려진 곳은 한 번씩만 계산한다.)

 

/* 해결 방안 */

겹쳐진 선분들끼리 한 구간으로 합쳐나가다가, 마지막에 구간들의 길이만 세서 더해주자!

→ Sweeping

 

/* 구현 과정 */

1. 왼쪽 좌표를 기준으로 선을 정렬한다.

2. 현재 구간의 가장 왼쪽(minn)과 가장 오른쪽(maxx)을 구해주고, 현재 보고있는 선이 여기에 포함되는지 아닌지 확인한다.

3. 만약 minn < 현재 보고있는 선의 왼쪽 이지만 maxx < 선의 오른쪽 좌표 라면, 'maxx = 선의 오른쪽 좌표' 로 선을 더 이어준다.

4. 만약 maxx보다 현재 보고 있는 선의 왼쪽 좌표가 크다면, 구간에서 아예 벗어난 뜻이므로 minn과 maxx를 바꿔준다.

 

/* 소스 코드 */

 

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define mod 10007
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<pi, int>pii;

int n, x, y, minn , maxx, ans;
vector<pi>v;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b; cin >> a >> b;
		v.push_back({ a, b });
	}

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

	minn = v[0].first;
	maxx = v[0].second;
	for (int i = 1; i < n; i++)
	{
    	//현재 구간에서 벗어난 선을 만남
		if (maxx < v[i].first) {
			ans += maxx - minn;
			minn = v[i].first;
		}
		maxx = max(maxx, v[i].second);
	}
	ans += maxx - minn;
	cout << ans;
}