급하게임개발

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

이 문제는 투 포인터 문제이다 이중 포문으로도 구현이 가능하나 해당 방식으로 할경우 시간 복잡도가 커진다 이에 루프문 한개로 해당 문제를 해결하는 게 핵심이다

이 문제의 로직은 일단 이어지는 선들을 최대한 길게 이어진  후 끊어졌을 때 부터 선을 다시 쭉 길게 이어서 이 선 2개의 길이의 합을 구하는 것이다

주어진 테스트 케이스를 v1.first를 기준으로 정렬하면 해당 그림 처럼 된다. 아래칸은 시작점 위에 칸은 끝나는 점을 의미한다. 이 리스트는 오름차순 정렬을 했다고 가정했기에 첫번째로 나오는 선은 1부터 시작해서 길게 늘일 것이다 즉 첫번째 상태일때

이렇게 된다 그후에 2부터 5까지를 비교했을 때 이 두선은 이어짐으로 start는 그대로 두고 end를 5로 바꿔준다 

그 다음 3부터 5까지도 이 선과 끝점은 같지만 시작점이 다름으로 기존에 있던 선임으로 포함을 시키지 않는다 아직도 start는 1 end 는 5이다
그 후 6과 7을 만났을때는 아래그림처럼 된다

6과 7을 만났을 때는 새  선임으로 기존에 있던 선의 길이를 일단 값을 누적시켜준후 리스틀 끝나지 탐색한후 해당 start와 end값을 다시 더해준다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	int sum = 0;
	cin >> n;

	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int n1, n2;
		cin >> n1>>n2;
		v.push_back({ n1,n2 });
	}
	sort(v.begin(), v.end());
	int start = v[0].first;
	int end = v[0].second;
	for (int i = 1; i < n; i++) {
	

		if (end > v[i].first) {
			end = max(v[i].second, end);
		}
		else {
			sum += end - start;
			start = v[i].first;
			end = v[i].second;
		}

	
	}
	sum += end - start;
	cout << sum;
}