[백준 BOJ/C++] 2170 선긋기

 

2170번: 선긋기

 

문제도 상당히 단순하고 쉬워보이지만 의외로 골드등급의 문제고 정답비율도 30% 대로 높지 않은편이다.
구현양도 얼마 안되지만 이러한 스타일의 문제를 많이 접해보지 않았다면 아이디어를 찾는데 어려움을 겪을 수도 있는 문제다.

 

문제는 정말 심플하다.

여러 선의 시작점과 끝점을 받아서 선들의 전체 길이를 구하면 된다.

하지만 이 선들은 일직선 상에 겹칠 수 있게 그려지며 따라서 겹쳐진 구간과 선이 그어지지 않은 구간을 제외한 실제전체 길이를 구해야 한다.

 

주어지는 값들의 범위도 꽤 크다.

점의 위치는 -1,000,000,000 ~ 1,000,000,000 사이이며 선의 수는 최대 1,000,000 으로 효율적으로 해결할 방법을 찾아야 한다.

 

 

---

 

 

문제의 포인트

 

아이디어 찾기

 

문제가 단순한 만큼 복잡한 알고리즘이나 자료구조가 필요하진 않다.

핵심 아이디어만 빠르게 발견한다면 수월하게 풀어낼 수 있는 문제이기도 하다.

 

 

우선 가장 먼저 떠올리기 쉬운 방법은 제일 작은 시작점과 큰 끝점을 찾아 길이를 계산하고 중복된 구간과 빈 구간의 길이를 빼주는 방법이다.

하지만 최대 선의 수가 적지 않아 반복적인 탐색을 하게되면 시간초과에 걸릴 위험이 크다.

특정 구간이 몇번 겹칠지도 알 수 없기 때문에 탐색 방식을 결정하기도 쉽지 않다.

 

 

오히려 조금 더 쉽게 접근해서 가장 작은 시작점부터 선을 그려가면서 끝점의 위치만 유지하고 있다면 겹치는 부분을 무시하고 길이를 늘려나갈 수 있을 것이다.

즉, 주어지는 선들을 앞에서부터 한붓 그리기처럼 그려간다는 생각으로 진행하면 중복이나 긴 구간을 별도로 확인할 필요 없이 의외로 간단히 풀린다.

 

 

 

 

 위와 같은 입력이 주어진 경우 첫번째 선을 3까지 그렸음을 기억하고, 그다음 선을 그을 때 3부터 5까지 길이 2만큼만 증가 시킨다.

그 다음 선은 3에서 5까지 이어지는 선인데 이미 5까지 그렸고 완전히 중복되는 선이므로 길이가 증가하지 않는다.

마지막은 6에서 7로 이어지는 선이고 현재 5까지 그렸으므로 이어지지 않게 6에서 7까지 길이 1만큼의 선만 더 그리면 된다.

 

 

위 과정을 한번 따라가보면 중간에 시작점이 더 작은 선이 들어오면 귀찮아짐을 알 수 있다.

따라서 시작점 기준 오름차순으로 정렬해두고 위 과정을 진행한다면 신경쓸일을 줄일 수 있다.

 

 

대체로 시작점과 끝점, 시작시간과 끝시간 등을 이용한 입력을 처리해야 하는 경우 데이터를 정렬해두고 풀어가야 하는 경우가 많다.

 

 

---

 

 

전체 Code

 

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

using namespace std;

int N;
vector<pair<int, int>> line;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, x, y, curr_pos = -1234567890;
	int sum = 0;

	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> x >> y;
		line.push_back(make_pair(x, y));
	}

	sort(line.begin(), line.end(), less<pair<int, int>>());

	for (i = 0; i < line.size(); i++) {
		if (curr_pos < line[i].first) {
			sum += line[i].second - line[i].first;
		}
		else {
			if (curr_pos < line[i].second)
				sum += line[i].second - curr_pos;
		}
		if (curr_pos < line[i].second)
			curr_pos = line[i].second;
	}

	cout << sum << "\n";

	return 0;
}