SOLDIERS/정진경

Describe SOLDIERS/정진경 here

Source Code

#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	int x[10001], y[10001];
	
	int i;
	int k;
	int resx, resy;

	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d %d", &x[i], &y[i]);
	}

	sort(x+1, x+n+1);
	sort(y+1, y+n+1);

	for(i=1; i<=n; i++){
		x[i]-=i;
	}
	sort(x+1, x+n+1);

	k=0;
	for(i=2; i<=n; i++){
		k+=x[i]-x[1];
	}
	resx=k;
	for(i=2; i<=n; i++){
		k+=(i-1)*(x[i]-x[i-1]);
		k-=(n-i+1)*(x[i]-x[i-1]);
		
		if(resx>k){
			resx=k;
		}
	}
	
	k=0;
	for(i=2; i<=n; i++){
		k+=y[i]-y[1];
	}
	resy=k;
	for(i=2; i<=n; i++){
		k+=(i-1)*(y[i]-y[i-1]);
		k-=(n-i+1)*(y[i]-y[i-1]);

		if(resy>k){
			resy=k;
		}
	}

	printf("%d", resx+resy);

	return 0;
}

8월 9일 ACM 스터디에 불참하게되어 위키에 내용만 올립니다. ㅜㅜ

힌트

X축으로 움직이는 것과 Y축으로 움직이는 것을 독립적으로 계산해도 최적해가 나옵니다.

중심으로 삼을 좌표를 찾는게 중요한데요, 저같은 경우 동적계획법을 통해 모든 경우를 살펴봤습니다.(정렬 후 선형 탐색)

• 이건 이제 다들 알고있다고--! 그 뒤가 문제란말야!!