BOJ 2170 선 긋기

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

2170번: 선 긋기

 

1차 시도

"중복되는 곳을 어떻게 저장했다가 사용할 것인가" 가 이 문제의 핵심이라고 생각했다.

그래서 배열을 만들어 할당된 곳을 체크하면서 길이를 측정하려고 하였다.

근데 문제는 크기였다. 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000) 라는 조건 때문에 배열 선언이 불가능해서 불가능하다고 판단

 

2차 시도

배열로 체크하는게 불가능하다면 가장 작은 값, 가장 큰 값을 지정하여 차등값 만큼 더해주는 방식을 생각하였다.

하지만 해당 접근 방식의 문제점은 서로 떨어진 경우이다.

 

만약 (0,1) (2,5) (0,3) 의 경우 (0,1) 과 (2,5) 사이의 1~2를 어떻게 저장해야 하나? 라는 의문점을 안겨줬다.

 

정답

두 번째 시도에서의 접근 방법을 이용하면서 서로 떨어진 것들도 표시하면 좋을 것 같다는 생각을 했다.

선이 이전과 겹치는 경우엔 선을 합쳐버리고, 떨어지는 경우엔 해당 선을 저장해놓기로 했다.

그리고 떨어져있는 선들의 길이를 모두 더해버리면 된다.

 

그래서 다음과 같은 알고리즘을 생각했다.

 

❗ 시작점 기준으로 Sort (a,b) 형식으로 입력된다고 가정. 1. 이전 b < 현재 a 인 경우     -> 덜어져있는 관계이므로, 저장한다. 2. 이전 b >= 현재 a 인 경우     -> 이어지는 관계이므로, 선을 합쳐버린다.

 

 

 

코드

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

using namespace std;

vector<pair<long long, long long>> pairSet;
vector<pair<long long, long long>> resVector;
long long smallest = 1000000001;
long long biggest = -1000000001;
// long long occupied[1000000001]; 너무 커서 안됨.
long long sum = 0;

long long n;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		long long a, b;
		cin >> a >> b;

		pairSet.push_back({ a,b });
	}

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

	// setting

	long long prevA = pairSet[0].first;
	long long prevB = pairSet[0].second;

	for (int i = 1; i < n; i++) {
		pair<long long, long long> currPos = pairSet[i];
		long long currA = currPos.first;
		long long currB = currPos.second;

		if (prevB < currA) {
			resVector.push_back({ prevA, prevB });
		}
		else {
			currA = min(currA, prevA);
			currB = max(currB, prevB);
		}

		if (i == n - 1) {
			
		}

		prevA = currA;
		prevB = currB;
	}

	resVector.push_back({ prevA, prevB });

	for (int i = 0; i < resVector.size(); i++) {
		//printf("%lld %lld : %lld\n", resVector[i].first, resVector[i].second, (resVector[i].second - resVector[i].first));
		sum += (resVector[i].second - resVector[i].first);
	}
	cout << sum;
}

- pairSet에 지점 x,y를 저장하고, x(시작점)을 기준으로 sort.

- 떨어진 관계의 경우, resVector에 해당 시작점과 끝점 쌍을 저장한다.