[백준] No.2170 - 선 긋기(C++)

문제

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

2170번: 선 긋기

 

풀이

해당 문제는 -1,000,000,000 이상 1,000,000,000 이하의 범위를 가지는 선들이 주어진다. 따라서 이를 단순히 20억 개의 배열에 저장해서 표현하기에는 메모리 제한으로 불가능하며 비효율적이다.

 

이 문제는 스위핑 알고리즘 대표적인 문제로 아래와 같은 방법으로 해결 가능하다. 

 

해당 문제에서 일단 배열 points에 입력을 받고 선의 시작 부분을 기준으로 정렬한다. 그 후 배열을 순회하며 아래의 조건을 확인한다.

 

선의 시작점(points[i].first)이 현재의 겹쳐 그리고 있는 선의 끝부분 (end_point)보다 큰 경우 

 

이 경우 선이 끊어진 것이므로 선들의 총 길이합(sum_length)에 end_point - start_point 로 이어진 선의 길이를 합해준다.

 

선의 끝점(points[i].second)이 겹쳐 그리고 있는 선의 끝부분 (end_point)보다 큰 경우 

 

이 경우는 선의 시작점(points[i].first)이 end_point보다 작기 때문에 선을 이어서 선의 끝점(points[i].second)까지 그린다.

따라서 end_point를 points[i].second로 저장해준다.

 

이외의 경우에는 선이 start_point와 end_point사이에 있는 것이므로

추가적인 연산이 필요 없다.

 

정렬의 경우 O(nlogn)의 시간 복잡도를, 순회는 O(n)의 시간 복잡도를 가지므로 전체 복잡도는 O(nlogn)이다.

 

즉, 스위핑 알고리즘은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 된다.

 

* 라이님의 블로그를 참조하였습니다.*

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220907708368

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)

 

코드

	#include <iostream>
	#include<algorithm>
	using namespace std;
	int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N;
	pair<int,int> points[1000000];
	cin>>N;
	int first,second;
	int sum_length=0;
	for(int i=0; i<N ; ++i){
	cin>>first>>second;
	points[i].first= first;
	points[i].second = second;
	}
	sort(points, points+N);
	int start_point = points[0].first, end_point = points[0].second;
	for(int i=1; i<N ; ++i){
	if(points[i].first > end_point){
	sum_length += end_point - start_point;
	start_point = points[i].first;
	end_point = points[i].second;
	}else if(points[i].second > end_point){
	end_point = points[i].second;
	}
	}
	sum_length += end_point - start_point;
	cout<<sum_length<<'\n';
	return 0;
	}

view raw [BaekJoon]_2170_선 긋기.cpp hosted with ❤ by GitHub