[BOJ] 2170 : 선 긋기 (C++)

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

2170번: 선 긋기

---

 

문제 풀이

입력된 선들을 그었을 때 나오는 선의 총 길이를 구하는 문제이다.

 

x와 y의 범위가 작을 때는, 다른 방법을 써도 될 것이다. 예를 들어, 범위만큼의 bool 형 배열을 선언하고, 선이 그어진 부분은 true로 표시하는 방법이 있다. 하지만, 이 경우에는 그러려면 배열의 크기가 20억이 되고, 선도 100만번이나 그을 수 있기 때문에 이 방법은 안 된다.

 

1. 선들을 하나하나 탐색하면서 선을 겹쳐 그려야 하는 아이디어를 떠올려야 한다.
2. 다만,,, 이 때 선들이 너무 와리가리치면서(?) 뒤죽박죽 들어오게 된다면 저장해야 할 것들이 많아진다. 선을 모두 입력받고 선들이 시작점을 기준으로 정렬하자.
3. 정렬이 끝나면 시작점이 작은 선들부터 하나하나씩 보면서 선들을 겹쳐 그리면 된다.
   1. 겹치는 경우는 뭐가 있을까? 다음 선의 시작점이 이전 선의 끝점보다 작은 경우이다. 이러면 선을 연장처리하면 된다.
   2. 그렇다면 다음 선의 시작점이 이전 선의 끝점보다 큰 경우, 즉 겹치지 않는 경우에는 선을 끝내고 지금까지 그린 선을 최종 반환값에 더해준다.

생각해보면 어려울 것 같지만, 구현하면 그렇지는 않은 문제 :)

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int> > v;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N;
	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].first, en = v[0].second, ans = 0;
	for (int i = 0; i < N; i++) {
		//이어지는 경우 
		if (en >= v[i].first) {
			en = max(v[i].second, en);
		}
		//이어지지 않는 경우 
		else {
			ans += en - st;
			st = v[i].first;
			en = v[i].second;
		}
	}
	ans += en - st;
	cout << ans;
	return 0;
}