SOLDIERS/정진경 - Revision history

Maintenance script: Repair batch-0003 pages from live compare

2026-03-27T00:29:09Z

Repair batch-0003 pages from live compare

← Older revision		Revision as of 00:29, 27 March 2026
Line 10:		Line 10:
	{		{
	int n;		int n;
	int x[10001], y[10001];		int x[10001], y[10001];

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

Line 25:		Line 25:

	for(i=1; i<=n; i++){		for(i=1; i<=n; i++){
	x[i]-=i;		x[i]-=i;
	}		}
	sort(x+1, x+n+1);		sort(x+1, x+n+1);
Line 31:		Line 31:
	k=0;		k=0;
	for(i=2; i<=n; i++){		for(i=2; i<=n; i++){
	k+=x[i]-x[1];		k+=x[i]-x[1];
	}		}
	resx=k;		resx=k;
	for(i=2; i<=n; i++){		for(i=2; i<=n; i++){
	k+=(i-1)*(x[i]-x[i-1]);		k+=(i-1)*(x[i]-x[i-1]);
	k-=(n-i+1)*(x[i]-x[i-1]);		k-=(n-i+1)*(x[i]-x[i-1]);

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

	if(resy>k){		if(resy>k){
Line 71:		Line 71:
	중심으로 삼을 좌표를 찾는게 중요한데요, 저같은 경우 동적계획법을 통해 모든 경우를 살펴봤습니다.(정렬 후 선형 탐색)		중심으로 삼을 좌표를 찾는게 중요한데요, 저같은 경우 동적계획법을 통해 모든 경우를 살펴봤습니다.(정렬 후 선형 탐색)
	* 이건 이제 다들 알고있다고--! 그 뒤가 문제란말야!!		* 이건 이제 다들 알고있다고--! 그 뒤가 문제란말야!!

imported>jereneal20 at 11:03, 9 August 2011

2011-08-09T11:03:32Z

← Older revision		Revision as of 11:03, 9 August 2011
Line 70:		Line 70:

	중심으로 삼을 좌표를 찾는게 중요한데요, 저같은 경우 동적계획법을 통해 모든 경우를 살펴봤습니다.(정렬 후 선형 탐색)		중심으로 삼을 좌표를 찾는게 중요한데요, 저같은 경우 동적계획법을 통해 모든 경우를 살펴봤습니다.(정렬 후 선형 탐색)
			* 이건 이제 다들 알고있다고--! 그 뒤가 문제란말야!!

imported>joojis at 01:45, 9 August 2011

2011-08-09T01:45:46Z

← Older revision		Revision as of 01:45, 9 August 2011
Line 65:		Line 65:
	8월 9일 ACM 스터디에 불참하게되어 위키에 내용만 올립니다. ㅜㅜ		8월 9일 ACM 스터디에 불참하게되어 위키에 내용만 올립니다. ㅜㅜ

	=== 풀이 ===		=== 힌트 ===

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

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

imported>joojis at 01:40, 9 August 2011

2011-08-09T01:40:29Z

← Older revision		Revision as of 01:40, 9 August 2011
Line 64:		Line 64:

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

			=== 풀이 ===

imported>joojis at 01:40, 9 August 2011

2011-08-09T01:40:03Z

New page

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 스터디에 불참하게되어 위키에 내용만 올립니다. ㅜㅜ