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

도화지에 선을 긋고 그은 선의 총길이를 출력하는 문제이다. 여러 번 그은 곳과 한번 그은 곳은 구분이 불가능하다.

 

선을 그을 때마다 배열에 저장하면서 문제를 해결할 수 있을까??

답은 불가능하다.

우선 선을 그을 때마다 배열에 일일이 저장하면(배열의 값을 1로 바꿔) 중복해서 그려지는 부분이 생긴다. 시간초과가 발생할 것.

 

그러면 시작점과 끝점에서 안 그려진 부분(0인지 1인지 확인)부터 그려진 부분까지 그리면 되는 거 아닌가?? 중간에 이미 그려졌으면 break; 시간초과가 안 발생할 것 같은데?

이것도 불가능하다. 배열에 20억개 이상 저장할 수 없다.

 

그러면 어떻게 해결해야 하는가?

앞에서부터 선을 긋는다. 그러려면 입력값을 일단 정렬해야 한다.

앞에서부터 선을 긋고 마지막에 그은 점을 저장해 놓는다.

다음에 그을 때 이 마지막 점을 이용한다.

만약 마지막 점이 현재 그리려는 점의 Start보다 뒤에 있다면 마지막 점에서부터 그리면 된다.

현재 그리는 end의 값이 마지막 점보다 크다면 마지막 점을 end값으로 갱신한다.

예를 들면 처음에 1부터 100까지 그릴 수도 있다. 이런 경우에는 마지막 점을 갱신하지 않는다.

 

음수 부분을 없애기 위해 10억을 더하고 시작했다.

시간초과 방지코드를 작성해줘야 한다.

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

#define k 1000000000

using namespace std;
vector<pair<int ,int>>v;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N = 0;
	cin >> N;
	int num1 = 0;
	int num2 = 0;

	int count = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> num1 >> num2;
		v.push_back({num1+k,num2+k});
	}

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

	long next = 0;
	for (int i = 0; i < N; i++)
	{
		num1 = v[i].first;
		num2 = v[i].second;
		if (num1 > next)
		{
			next = num1;
		}
		if (num2 - next > 0)
		{
			count += num2 - next;
		}
		if (num2 > next)
		{
			next = num2;
		}
	}
	cout << count;


	return 0;
}