[BOJ] 백준 2170 선 긋기

문제 링크

15922 아우으 우아으이야!! 문제와 같은 문제입니다. 예전에 썼던 풀이 그대로 퍼올게여.

문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다.

인접한 두 수직선의 관계는 다음과 같다.

빨간 선의 양 끝점을 $s, e$라 하고, 파란 선의 양 끝점을 $ns, ne$라 하자.

①은 $s \leq ns$ & $ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다.

②는 $ns < e$인 경우이고, 중복해서 더해지는 $e - ns$값을 빼주면 된다.

③의 경우엔 그냥 둘 다 더하면 된다.

파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다.

정답 코드

	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	using ll = long long;
	const ll INF = 0x3f3f3f3f;
	int n;
	vector<pair<ll, ll>> p;
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	ll s, e;
	for (int i = 0; i < n; i++) {
	cin >> s >> e;
	p.emplace_back(s, e);
	}
	sort(p.begin(), p.end());
	ll ans = 0;
	s = -INF, e = -INF;
	for(int i=0;i<p.size(); i++){
	auto cur = p[i];
	ll ns = cur.first, ne = cur.second;
	if (s <= ns && ne <= e)continue; // case 1
	ans += ne - ns;
	if (ns < e) { // case 2
	ans -= (e - ns);
	}
	s = ns;
	e = ne;
	}
	cout << ans;
	}

view raw 15922.cpp hosted with ❤ by GitHub