[ boj : 2357 ] 농구 골대 세우기

www.acmicpc.net/problem/2375

2375번: 농구 골대 세우기

문제 : 좌표들이 주어지고 주어진 조건이 최소가 되게끔 농구골대를 설치해라

 

해설 : 이게 왜 골드2인지는 모르겠습니다. 비슷한 문제는 저어어어어 아래있는데 말이죠 ㅎㅎ

일단 모든 좌표들을 전부 비교해서 O(n^2) 의 시간복잡도로 해결하기에는 무리입니다.

n의 범위가 십만이니까요. 그럼 다른 방법을 택해야 되는데 사전지식을 하나 배워갑니다.(머릿속에 잘 박아두세염)

 

Q. 수평선이 주어지고  N개의 점들이 주어집니다. 이때 어떤 한점을 선택했을때 나머지 점들과의 거리가 최소가 되게끔 하는 점을 구하시오.

 

sol)

먼저 어떤 점을 잡았다고 생각해봅시다. 그리고 이 어떤점보다 왼쪽에 존재하는 수들의 개수를 x 개 라고 하면 어떤 점을 포함한 오른쪽에 있는 점들은 N-x 개가 되겠죠. 

(중요)만약 x<(N-x) 라고 가정을 한다면, 이 어떤점을 오른쪽으로 한칸 옮겼을때 왼쪽에 있는 점들과는 1씩 멀어지게 되고 오른쪽에 있는 점들과는 1씩 가까워 질겁니다. 근데 x<(N-x) 라고 했으니 '멀어진 거리' 보다 '가까워진 거리'가 더 많게 됩니다. 즉, '이득'이라는 뜻입니다.

 

그럼 곰곰이 생각해 보면 어느쪽으로 옮기든지 간에 손해가 되는 점을 구할 수 있으면 그 점이 바로 '다른 점들과 거리가 최소가 되는 점' 이 되는 것 입니다. 바로 x=(N-x) 인 점을 찾으면 되는 것 이죠. 이를 이항하면 2x = N 이고 x=N/2 가 됩니다.

 

즉, 중앙값이 답입니다.

 

다시 문제로 돌아가서 2차원 좌표에서 점들이 주어지고 각 거리가 최소가 되는 점을 구해야 됩니다.(당장 마을에 사는 주민들의 수는 빼고 봅시다)

그럼 x축,y축 각각에 대해 중앙값들을 구한 뒤 합쳐주면 그점이 바로 '최소가 되게끔 만드는 점'이 됩니다.

 

그러나 조건이 하나 더 있죠. 바로 마을에 사는 주민들의 수 인데요.

( 각 마을에서 농구골대까지의 거리 × 그 마을의 사람 수 ) 라는 뜻은 결국 '마을에 사는 주민들 모두가 농구 골대까지 가는 거리' 라는 뜻입니다. '×' 연산자로 생각하지 말고 '+' 연산자로 생각해보면 쉽게 접근이 가능하죠.

 

즉, 마을의 사는 주민의 수가 3명이라면 (1,1) 이 주어졌을때 (1,1) (1,1) (1,1) 이렇게 3개의 점으로 나열해 주면 됩니다.

 

그럼 다 구했습니다. 마을의 주민 수 만큼 점들을 나열해 준뒤 x 축으로 정렬, y축으로 정렬을 한 뒤에 각각의 중앙값들을 구해 답을 구해주면 됩니다.

이때, 좌표들의 수가 홀수이면 중앙값은 (cnt+1)/2 이 됩니다 ㅎㅎ

 

+이 문제를 풀었으면

www.acmicpc.net/problem/14400

14400번: 편의점 2

이 문제도 쉽게 풀 수 있으실 겁니다.

#include<bits/stdc++.h>

using namespace std;

int x[(int)1e7], y[(int)1e7];

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

	int n,a,b,c;
	int cnt = 0;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		for (int j = 0; j < c; j++) {
			x[cnt] = a;
			y[cnt++] = b;
		}
	}
	sort(x, x + cnt);
	sort(y, y + cnt);
	cnt += (cnt % 2 != 0) ? 1 : 0;
	cout << x[cnt / 2-1] << " " << y[cnt / 2-1];
	return 0;
}