확률론 - 5000!개의 거리의 합의 평균을 구하는 방법

1. 문제

 

28139번: 평균 구하기 (acmicpc.net)

28139번: 평균 구하기

 

2. 풀이

 

최악의 경우 5000!가지를 모두 거리를 계산해봐서 평균을 구해야하는데, 당연히 2.5초안에 가능할리는 없고

 

5000!가지를 안구해봐도 구하는 방법이 있겠지

 

확률변수 $X$를 $N!$가지 각각 경우의 수에서 나올 수 있는 이동거리라고 정의하자.

 

문제에도 나와있듯이

 

"총이동거리는 해당 순서에서 첫 번째 사람과 두 번째 사람 간의 거리, 두 번째 사람과 세 번째 사람 간의 거리, ... , N-1번째 사람과 N번째 사람간의 거리의 합이다"

 

라고 나와있는데, $X$를 위와 같이 분할해보는 것이다

 

첫 번째 사람과 두 번째 사람간의 거리 $X_{1}$

 

두 번째 사람과 세 번째 사람간의 거리 $X_{2}$

 

...

 

$N-1$번째 사람과 $N$번째 사람간의 거리 $X_{N-1}$이라고 정의하자.

 

$$X = \sum_{k=1}^{N-1} X_{i}$$ 라고 정의할 수 있다.

 

그러면 문제에서 원하는 값은 X의 평균으로, E(X)이다.

 

그러므로 기댓값의 성질을 이용하면, $$E(X) = \sum_{k=1}^{N-1} E(X_{i})$$

 

사람간의 구별이 없기 때문에 $i$와 $j$가 서로 다를때,

 

$i$번째 사람과 $i+1$번째 사람간의 거리의 기댓값과 $j$번째 사람과 $j+1$번째 사람간의 거리의 기댓값은 동일하다.

 

즉, $$E(X_{i}) = E(X_{j})$$

 

그러므로 $$E(X) = (N-1)E(X_{1})$$

 

그래서, 첫번째와 두번째 사람간의 거리로 가능한 모든 경우를 더하고 평균을 구한 다음에 $N-1$을 곱하면 그것이 정답이다

 

from sys import stdin

#두 점 a,b의 거리를 구하는 함수
def distance(a,b):
    
    return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**(1/2)

n = int(stdin.readline())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))


#가능한 두 점 사이의 거리의 총 합을 개수로 나눠 평균을 구한다
total = 0
count = 0

for i in range(n-1):
    
    for j in range(i+1,n):
        
        total += distance(points[i],points[j])
        count += 1

mean = total/count

#기댓값의 선형성을 이용하면 N!가지의 모든 경우에 대한 기댓값을 구하게 된다
print((n-1)*mean)