[BOJ] 2170번_선 긋기_정렬 (C++)

[문제]

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

한 점에서 다른 한점을 이어 선을 그으려고 한다. 선을 그을 때 이미 선이 있는 위치에 겹쳐서 그리는 경우도 있는데, 여러번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자. 이 때 최종적으로 그려지는 선(들)의 총 길이를 구하는 문제이다.

[사용 알고리즘]

정렬

[풀이 핵심]

• 구조체를 이용해서 선의 시작점과 끝점을 vector에 저장한다. 저장한 선들을 시작지점을 비교해서 오름차순으로 정렬한 후 앞의 선부터 그려주면 된다.
• 선을 그릴 때 3가지 경우의 수가 존재한다.

  1. 새로운 선을 그리는 경우 (이전에 그렸던 선의 end < 그리려는 선의 start)
  2. 이미 그려져 있는 선에서 시작해서 더 길게 그리는 경우 (이전에 그렸던 선의 end >= 그리려는 선의 start && 이전에 그렸던 선의 end < 그리려는 선의 end)
  3. 그리려는 선이 이미 그려져 있는 선에 포함되는 경우 (선을 안그려도 되므로 넘김)

위 세가지 경우를 처리해주면 최종적으로 그려지는 선들을 구할 수 있다.
나는 2,3번을 한번에 max함수를 이용해서 처리했다.

[코드]

//boj2170번_선 긋기_정렬

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct line {
	int start;
	int end;
};

bool compare(line a, line b) {
	if (a.start < b.start) {
		return true;
	}
	else {
		return false;
	}
}

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

	int N;
	cin >> N;

	vector<line> v;

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;

		line l;
		l.start = x;
		l.end = y;

		v.push_back(l);
	}

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

	int s = v[0].start;
	int e = v[0].end;

	int result = 0;

	for (int i = 0; i < N; i++) {
		if (e < v[i].start) {
			result += e - s;

			s = v[i].start;
			e = v[i].end;
		}
		else {
			e = max(e, v[i].end);
		}
	}

	result += e - s;

	cout << result;

	return 0;
}