[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
바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.
github.com
vector에다가 값을 넣는데, left 값이면 1로 right 값이면 -1로 넣는다. 이 값들은 cnt에 추가해지면서 선의 길이를 추가할지 말지에 이용된다. 즉 , right 값이 들어가면 cnt가 감소하게 되고 , cnt == 0이라면 괄호가 하나의 연결구간이 막을 내렸다고 해석할 수 있다.