백준 2170번, 선 긋기 풀이

문제

백준 2170번

풀이

수직선 상에 테스트 케이스를 나타내봅시다.

테스트 케이스 시각화

 

현재 선이 그이고 있는가? 그이지 않고 있는가?를 생각해보며 문제를 풀어주면 쉽게 풀 수 있습니다.

선이 그이고 있는가 없는가 는 긋기 시작하면 1을 증가시켜주고, 긋는 것을 멈출 때 1 감소시켜주는 변수 하나로 관리할 수 있습니다.

 

주석으로 설명을 대체합니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector <ll> vl;

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

	int n; cin >> n;
	vector<pii> vec;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		if (a > b) swap(a, b); //a > b인 경우를 고려해야 합니다.
		vec.emplace_back(a, 1);
		vec.emplace_back(b, 0);
	}

	sort(all(vec));

	ll open = 0, first = 0, ans = 0;
	for (const auto &[a, b] : vec) {
    //열면 depth를 1 증가
		if (b) {
			if (!open) first = a; //선을 긋기 시작한 위치를 저장
			open++;
		} else {
        //닫으면 depth를 1 감소
			--open;
            //depth가 0이 된다면, 시작점부터 해당 지점까지 선이 그여진 것이므로 해당 선분의 길이를 더함
			if (!open) {
				ans += a - first;
			}
		}
	}

	cout << ans;
}