[백준 2170번 / C++] 선 긋기

투포인터를 활용한 문제이다. 

 

1. pair 구조를 가진 벡터를 오름차순으로 정렬하자. 

2. 첫번째 벡터 쌍의 원소 값 두개(X, Y)를 start 와 end 라는 변수에 각각 저장하자. 

3. 벡터 사이즈만큼 반복문을 돌린다.

 

이때, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 작거나 같으면 선이 이어진다는 의미이므로, 벡터의 두번째 원소의 값과 end 변수에 저장된 값 중 큰 값으로 end 변수를 갱신해나간다. 

만약, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 크다면 선이 겹치지 않았다는 의미이므로 start, end 변수에는 해당 벡터의 원소의 값들로 새로 저장해준다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0);  
	int n; cin >> n; 
	vector <pair<int, int>> v; 
	for (int i = 0; i < n; i++) {
		int a, b; 
		cin >> a >> b; 
		v.push_back({ a,b }); 
	}
	sort(v.begin(), v.end()); 	
	int start, end, sum = 0; 
	start = v[0].first; 
	end = v[0].second; 
	for (int i = 1; i < v.size(); i++) {
		if (end >= v[i].first)end = max(end, v[i].second); 		
		else {	
			sum += (end - start); 
			start = v[i].first; 
			end = v[i].second; 
		}
	}
	sum += (end - start); 
	cout << sum; 
}

2170번: 선 긋기