[백준 알고리즘] 2170 C++ 선긋기

문제 이해

선이 그려지는 공간은 2차원 공간이 아닌 1차원 직선 -> x, y 의 변수가 (x,y)가 아닌 시작 점, 끝 점 의 구성

---

시작점을 기준으로 정렬이 필요함

-> 선이 겹쳐지는 경우 카운트는 한 선만 되기 때문

---

크게 3가지의 경우의 수가 존재

1. 현재 i 노드의 시작점이 이전의 최대 점보다 클 때 -> 선의 길이 그대로 더하기

2. 현재 i 노드의 시작점이 이전의 최대 점보다 작고, 끝 점이 최대 점보다 클 때 -> i 노드의 끝점 - 이전의 최대 점  더하기

3. 현재 i 노드의 시작점이 이전의 최대 점보다 작고, 끝 점도 최대 점보다 작을 때 -> 연산 안하기

 

매 반복문의 끝에 이전의 최대값을 갱신시켜주는 로직 필요!!

 

#include <iostream>
#include <algorithm>

std::pair<int,int> list[1000001] = {};
int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	int a, b;
	for (int i{ 0 };i < n;i++) {
		std::cin >> a >> b;
		list[i].first = std::min(a, b);
		list[i].second = std::max(a, b);
	}

	std::sort(list, list + n);

	long long sum = std::abs(list[0].second-list[0].first);
	int m = list[0].second;
	for (int i{ 1 };i < n;i++) {
		if (list[i].first <= m && list[i].second >= m) {
			sum += std::abs(list[i].second - m);
		}
		else if (list[i].first >= m) {
			sum += std::abs(list[i].second - list[i].first);
		}

		m = std::max(m, list[i].second);
	}

	std::cout << sum << "\n";
}