[백준 / C++] 편의점 2 (실버2, 14400)

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

문제

영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 정의한다.

n명의 주요 고객들의 위치 (xi, yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력

첫째 줄에는 주요 고객들의 수 n이 주어진다.

다음 n줄에는 i번 고객의 위치 xi, yi가 주어진다.

출력

모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

제한

• 1 ≤ n ≤ 100 000
• -1 000 000 ≤ xi, yi ≤ 1 000 000

예제 입력 1

5
2 2
3 4
5 6
1 9
-2 -8

예제 출력 1

30

---

문제 풀이

이번 문제는 주어진 모든 집에서 방문하기 가장 효율적인 편의점 위치를 계산하는 문제입니다.

 

주어진 제한사항을 보면 n이 100,000까지 늘어날 수 있으며, x와 y 좌표가 -1,000,000 ~ 1,000,000이므로 모든 좌표에 대해 체크하는 방식으로 문제에 접근하면 시간초과가 발생합니다.

 

저의 경우 가장 효율적인 위치를 찾기 위해 다음과 같이 이진 탐색 방식을 활용했습니다. 분명 틀릴리가 없다고 생각했지만 제가 놓친 부분이 있었습니다. 저는 sumX와 sumY를 int 형식으로 처리했지만 n이 100,000이고 좌표가 전부 멀리 떨어져 있는 경우 int의 최대값인 21억을 넘어가는 수치가 나올 수도 있기에 해당 부분을 수정하여 문제를 해결하게 되었습니다.

 

간단한 문제였지만, 이후 다른 분의 풀이 과정을 보니 x좌표를 정렬하고, y좌표를 정렬한 후 중앙의 값이 가장 효율적인 값이라는 것을 알게 되었고, 자료형 문제에 시간을 많이 뺐겼기에 다음부터 필수적으로 확인해야 겠다는 생각을 하게 되었습니다.

코드

풀이 시간 : 43m 30s

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<pair<int, int>> v;
long long int sumX;
long long int sumY;

void SumDistance(bool bIsFirst)
{
	int L = -1000000;
	int R = 1000000;

	while (L <= R)
	{
		int mid = (L + R) / 2;

		// mid에서의 값 도출
		long long int midSum = 0;
		long long int midLSum = 0;
		long long int midRSum = 0;

		for (int i = 0; i < v.size(); i++)
		{
			if (bIsFirst)
			{
				midSum += abs(mid - v[i].first);
				midLSum += abs(mid - 1 - v[i].first);
				midRSum += abs(mid + 1 - v[i].first);
			}
			else
			{
				midSum += abs(mid - v[i].second);
				midLSum += abs(mid - 1 - v[i].second);
				midRSum += abs(mid + 1 - v[i].second);
			}
			
		}

		// 만약 mid가 가장 작다면?
		if (midSum < midLSum && midSum < midRSum)
		{
			// 합이 최소인 mid를 찾았으므로 종료
			if (bIsFirst)
				sumX = midSum;
			else
				sumY = midSum;
			break;
		}
		// 아닌 경우 절반으로 범위 줄이기
		else
		{
			if (midLSum < midRSum)
			{
				// 왼쪽이 더 작음 -> 시작 인덱스 ~ mid -1
				R = mid - 1;

				if (bIsFirst)
					sumX = midLSum;
				else
					sumY = midLSum;
			}
			else
			{
				// 오른쪽이 더 작음 -> mid + 1 ~ 종료 인덱스
				L = mid + 1;

				if (bIsFirst)
					sumX = midRSum;
				else
					sumY = midRSum;
			}
		}
	}
}

int main()
{
	cin >> n;

	// 모든 집의 좌표 저장
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;

		v.push_back(make_pair(x, y));
	}

	SumDistance(true);
	SumDistance(false);

	cout << sumX + sumY;
}