BOJ 28139 | 평균 구하기

5월 월간 향유회 B번 문제입니다.

우선 문제를 보면 머리가 아픕니다. 저는 조합론을 별로 안 좋아합니다. 그래도 문제를 봅시다.

만약 고등학교 때 확률과 통계를 배웠다면 비슷한 문제를 내신에서 풀어봤을 것입니다.

어떤 한 사람의 위치에서 출발해서 모든 사람의 위치를 방문하는 경우는 $N!$이라고 문제에서 그랬습니다.

그러면 한 사람의 위치를 고정하면, 경우의 수는 $N-1!$일 것입니다.

두 번째 사람의 위치도 고정해봅시다. 그러면 경우의 수는 $N-2!$입니다.

이제 간선 하나가 고정된 상태입니다. 그런데 사람 2명의 위치는 경로의 시작 지점이 아니라 중간 어느 지점이어도 괜찮습니다. 이 경우의 수는 $N-1$입니다. 사람 2명의 순서가 바뀔 수 있으니 $2$를 추가로 곱해주어야 합니다.

결국 어떤 간선이 경로에 참여하는 경우의 수는 $2 * (N-1)!$입니다. 전체 경우의 수가 $N!$이므로 모든 간선의 길이에 $2/N$을 곱해서 전부 더하면 총 이동 거리의 평균이 됩니다.

시간 복잡도는 $O(N^2)$입니다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Dot{
	int x, y;
};

int main(){
	int N; cin >> N;
	vector<Dot> a;
	double rst = 0;
	
	for (int i = 0; i < N; i++){
		int x, y; cin >> x >> y;
		a.push_back({x, y});
	}
	
	for (int i = 0; i < N; i++){
		for (int j = i+1; j < N; j++){
			Dot d1 = a[i], d2 = a[j];
			double ds = sqrt((d1.x-d2.x)*(d1.x-d2.x)+(d1.y-d2.y)*(d1.y-d2.y));
			rst += ds / N;
		}
	}
	
	printf("%.10lf", rst*2.0);
}