[BOJ] 2170번 : 선 긋기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second
int n; 
vector<pair<int, int>> v; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y; 
		cin >> x >> y; 
		v.push_back({ x,y }); 
	}
	sort(v.begin(), v.end()); 
	int st = v[0].X, en = v[0].Y; 
	int ans = 0;
	for (int i = 1; i < v.size(); i++) {
		if (v[i].X <= en && v[i].Y > en) { // v[i].X가 범위안에 있으면서 v[i].Y가 범위를 넓힐때
			en = v[i].Y;
		}
		else if (v[i].X > en) { // v[i].X가 범위안에 있지않을때, 즉 새로 시작해야할때
			ans += en - st;
			st = v[i].X, en = v[i].Y;
		}
	}
	ans += en - st; 
	cout << ans << '\n';
}

초기 범위를 설정해 주고 (st와 en에) en보다 다음선의 시작점이 같거나 작고, en 보다 다음 선의 끝점이 크면 범위를 연장시켜 준다. 따라서, en = v [i]. Y;로 갱신한다. 만약에 범위에 포함되지 않는다면, 새롭게 시작해야 하기 때문에, ans에 값을 추가한 뒤, st와 en을 현재 선으로 초기화시킨다. (물론, 이 logic은 sort를 했기 때문에 가능하다) 

선이 끊기지 않을 시, ans에 값을 추가하지 못하므로, 마지막에 한번 더 추가해 준다. 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/c5472861d2ee4a1e8f8c3c60f477f0bc
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  vector<pair<int,int>> events;  
  int n;
  cin >> n;
  while(n--){
    int l, r;
    cin >> l >> r;
    events.push_back({l, 1});
    events.push_back({r, -1});
  }
  sort(events.begin(), events.end());
  int cnt = 0; // 현재 선의 개수
  int tot = 0; // 전체 길이(= 답)
  int loc = -1e9; // 현재 위치
  for(auto event : events){
    if(cnt > 0) tot += (event.X - loc);
    loc = event.X;
    cnt += event.Y;
  }
  cout << tot;
}
/*
선의 시작과 끝을 이벤트로 관리해 선이 1개 이상 있는 구간을 계속 더해준다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/2170.cpp

basic-algo-lecture/0x11/solutions/2170.cpp at master · encrypted-def/basic-algo-lecture

vector에다가 값을 넣는데, left 값이면 1로 right 값이면 -1로 넣는다. 이 값들은 cnt에 추가해지면서 선의 길이를 추가할지 말지에 이용된다. 즉 , right 값이 들어가면 cnt가 감소하게 되고 , cnt == 0이라면 괄호가 하나의 연결구간이 막을 내렸다고 해석할 수 있다.