[C++] 2170 : 선 긋기

골드 Ⅴ

 

처음의 배열로 푼 코드

 

#include <iostream>
#include <utility>
#include <algorithm>

using namespace std;

int n, x, y;

int main() {
	scanf("%d", &n);
	
	pair<int, int> line[1000000];
	
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		line[i] = make_pair(x, y);
	}
	
	sort(line, line + n);

	pair<int, int> len = line[0];
	int ans = 0;

	for (int i = 0; i < n - 1; i++) {
		if (len.second < line[i + 1].first) {
			ans += (len.second - len.first);
			len = line[i + 1];
		}
		else if (len.second < line[i + 1].second) {
			len.second = line[i + 1].second;
		}
	}
	ans += (len.second - len.first);
	printf("%d", ans);
}

배열을 벡터로 바꿔서 푼 코드

 

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

int n, x, y;

int main() {
	scanf("%d", &n);
	
	vector <pair<int, int>> line;

	for (int i = 0; i < n; i++) {
		scanf("%d%d", &x, &y);
		line.push_back(make_pair(x, y));
	}

	sort(line.begin(), line.end());

	pair<int, int> len = line[0];
	int ans = 0;

	for (int i = 0; i < n - 1; i++) {
		if (len.second < line[i + 1].first) {
			ans += (len.second - len.first);
			len = line[i + 1];
		}
		else if (len.second < line[i + 1].second) {
			len.second = line[i + 1].second;
		}
	}
	ans += (len.second - len.first);
	printf("%d", ans);
}

결과를 보니까 벡터로 한 게 메모리는 두배 넘게(...) 잡아먹고 시간도 약간 더 걸렸는데

음... 일단 벡터로 바꾼 이유가

 

위의 배열로 짠 코드는 애초에 비주얼 스튜디오에서 돌아가지를 않는다!

int 배열의 경우 최대 크기가 25만인데 이 문제에서는 100만이 필요하므로..

문제 풀 때는 10만으로 줄여놓고 푼 다음에 제출만 100만으로 하긴 했는데

 

음 아무튼.. 근데 구글링해보니 의외로 벡터가 1억? 최대 크기가 길길래 벡터로 바꿔줬다

 

뭐 이것도 중요하긴 한데 가장 중요한건

이 문제에서 쓰인 알고리즘 스위핑 이다

구글링을 좀 해보니... 간단하게 말하면

"도형들을 일정 기준에 맞춰 정렬해 놓고 순서대로 훑는 것 (스캔하면서 마주치는 요소들에 대해 뭔가를 해준다)"

과 동치가 된다고 한다

 

이 문제에 대입해서 생각해 보면 이 문제는 2차원 도형(pair <int, int>) 를 first에 맞춰서 정렬해 놓고

순서대로 훑으며 (순서대로 벡터든 배열을 훑으며)

마주치는 요소들에 대해 뭔가를 해주는(len과 i+1의 요소를 어쩌구 저쩌구 해주는)

알고리즘을 사용했으므로 스위핑 알고리즘을 사용했다고 할 수 있겠다

 

알겠나??ㅎㅎ

 

나중에 이 문제도 풀어보자

www.acmicpc.net/problem/5419

5419번: 북서풍

 

이 문제는 세그먼트 트리에 대한 이해도 필요한 것으로 보임