본문 바로가기

카테고리 없음

[백준 1007번] 벡터 매칭 (Python3)

import sys
input = sys.stdin.readline
from itertools import combinations
import math
INF = 10**9

T = int(input())
for test in range(T):
  N = int(input())

  xlist = []
  ylist = []
  for i in range(N):
    x,y = map(int,input().split())
    xlist.append(x)
    ylist.append(y)

  xsum = sum(xlist)
  ysum = sum(ylist)
  result = INF
  for select in combinations(range(N),N//2):
    xsum1 = xsum
    ysum1 = ysum
    for i in select:
      xsum1 -= xlist[i]*2
      ysum1 -= ylist[i]*2
    result = min(result,math.sqrt(xsum1**2+ysum1**2))

  print(result)

 

수학적 배경지식이 있다면 너무나 쉽게 풀 수 있는 문제

 

결국 N개의 점에서 N/2개의 벡터의 합이라는 뜻은, +로 잡을 점 N/2개와 -로 잡을 점 N/2개를 구하고 모두 합해버리면 된다는 뜻이다.

즉 combinations을 이용해 nCn/2 를 써서 어떤 점을 음수로 잡을지를 정한 뒤 최솟값을 구하면 된다.

 

다른 사람들의 풀이를 보니 문제의 의도는 백트래킹을 이용한 브루트포스 알고리즘으로 풀라고 낸 문제인 것 같은데, 이 부분에 대해서도 고려해봐야겠다.

 

여담으로 이 문제는 python으로 채점했을때와 pypy로 채점했을때 시간이 무려 20배나 차이가 났는데, 어디서 이런 차이가 오는건지 궁금하다.

 

 

오늘의 교훈) 수학이 중요하다