[BOJ] 백준 15922 아우으 우아으이야!!

문제 링크

https://www.acmicpc.net/problem/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

질문, 피드백 환영합니다.