[ boj : 1090 ] 체커

www.acmicpc.net/problem/1090

1090번: 체커

문제 : n개의 체커들이 주어지고 이 체커들은 상하좌우 한칸씩 이동이 가능합니다. 이때 k 개의 체커를 선택하고 이 체커들이 한곳에 모이도록 할때, 최소 이동수를 구하시오

 

해설 : 어렵습니다!!

음,,일단 먼저 '중앙값의 정리' 를 알고 있다고 생각하고 해설을 진행할 테니 꼭 이 개념에 대해 배우고 오세요

(boomrabbit.tistory.com/88) 여기에 정리해놨습니다.

 

결국 n개의 좌표중에서 k개를 선택했을때 이 k 개의 좌표들 중 중앙값에 해당하는 x,y좌표가 거리를 최소 이동하게끔 해주는 좌표입니다.

근데 문제가 생깁니다. n개중에 k개의 좌표를 먼저 선택해야되는데 단순히 '조합'으로 선택하기에는 너무나도 많은 시간이 걸린다는 것 입니다. 당장 59C25 만 해도 십억이 훌쩍 넘어가버리게 되니까요.

 

우린 생각을 뒤집어서 좌표들을 먼저 뽑고 중앙값을 구하는게 아니라, '중앙값의 후보'들을 먼저 나열한 후 이 중앙값과 가장 가까운 거리에 있는 좌표들 k개를 선택하는 것 입니다. 즉, 결국 중앙값들은 n개의 좌표들에서 주어진 수들에서 나올테니 O(n^2)으로 중앙값의 후보들을 쫙 뽑아낸 후에 n개의 좌표들을 돌아가면서 거리들을 구해주고 가장 작은 값을 순차적으로 k개 더해주면 답이 되는 것 입니다.

 

전 중앙값들의 후보들을 O(n^2)으로 뽑아낸후 이 것들을 0~n개까지 돌려주면서 확인했습니다. 시간복잡도는 O(n^4)가 되겠네요. 그러나 저처럼 하면 비효율적입니다. 다른 분들 소스를 보니 O(n^3)에 하셨는데 그냥 x,y 좌표를 for문으로 돌리면서 바로 n개의 좌표들에 대해 중앙값들을 구해주었더라구요. 이렇게 하면 시간이 훨씬 줄어들게 됩니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
ll x[50], y[50];
vector<pair<ll, ll>> v;

ll solve(int N, pair<ll, ll> cur);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	for (int i = 0; i < n; i++)cin >> x[i] >> y[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			v.push_back({ x[i],y[j] });
	for (int i = 0; i < n; i++) {
		ll ans = (ll)1e9;
		for (int j = 0; j < v.size(); j++)
			ans = min(ans, solve(i, v[j]));
		cout << ans << " ";
	}
	return 0;
}
ll solve(int N,pair<ll, ll> cur)
{
	vector<ll> t;
	for (int i = 0; i < n; i++) 
		t.push_back(abs(x[i] - cur.first) + abs(y[i] - cur.second));	
	sort(t.begin(), t.end());
	ll ret = 0;
	for (int i = 0; i < N+1; i++)
		ret += t[i];
	return ret;
}