백준 28139 평균 구하기

시간초과를 해결하기 위한 방법을 고민한 문제였다.
결국 모든 경우에서의 경로를 고민해야 하므로 각 경로를 지나는 횟수는 같다는 가정에서 풀이할 수 있었다.

📜 문제 바로 가기 : 백준 평균 구하기

제출 코드

import sys
input = sys.stdin.readline

def distance(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

def factorial(n):
    v = 1
    for i in range(1, n+1):
        v *= i
    return v

N = int(input()) # 점의 개수

pos = [(0,0)] # 위치 좌표
for _ in range(N):
    x, y = map(int, input().split())
    pos.append((x, y))

v = 0
for i in range(1, N):
    for j in range(i+1, N+1):
        v += distance(pos[i][0], pos[i][1], pos[j][0], pos[j][1])

print((v * 2) / N)

---

접근 방법

"모든 경우의 수를 생각한다면 특정 경로를 지나가는 횟수는 다른 특정 경로를 지나는 횟수와 같을 것이다." 라는 생각해서 출발했다.

예를들어 N = 4 라면 각 지점을 연결하는 경로의 수는 6가지가 나오고 만약, 모든 경우의 수에서 이동 횟수를 세어보니 600이었다면 각각의 경로수는 총 100번씩 지날것이다.

즉 모든 경우의 수를 고려한다면 어느 경로든지 특별하게 더 많이 이동하는 경로도, 더 적게 이동하는 경로도 없을 것이다. (사실, 수학적으로 증명한것은 아니고 짐작하여 이럴것이다~ 하고 생각하고 풀어봤는데 풀려서 쓰긴하지만.. 왜 이렇게 되는지 수학적으로 증명은 못하겠다.)

이를 이용하면 모든 경로의 거리를 모두 더하고 단순 계산으로 진행하면 굳이 각 경우의수를 계산할 필요없이 단순 곱셉으로 평균갑을 도출할 수 있다.

(v * 2) / N 도출 방법

먼저 모든 지점을 다 방문하는 경우의 수는 N! 개이다.
각 경우의 수에서 지나는 경로의 수는 N-1 개 이다. (모든 지점을 방문해야 하므로)
그러므로 전체 지나는 경로 수는 N! x (N-1) 개 이다.

N에서 나올 수 있는 서로다른 경로의 수는 N x (N-1) / 2 개 이다.
그러므로 각 경로의 수에서 지나야하는 횟수는 (N! x (N-1) x 2) / (N x (N - 1)) 개 이다. ( == (N! x 2) / N)

전체 경로의 합을 v 라고하면 모든 경우의 수에서 총 경로합은 (v x N! x 2) / N 이 된다.
끝으로 문제에서 평균을 구하라고 하였으므로 전체 경우의 수 N! 으로 나눠주면 (v * 2) / N 을 도출할 수 있다.