[python] 백준 1007번 : 벡터 매칭

2022.05.24.에 푼 것

 

일단 이 문제도 그렇게 어려운 편은 아니었다.
하지만 고등학교 이후 벡터를 넘 오랜만에 봐서 그런지^^
벡터 계산에 살짝 헤맸다.ㅎ.ㅎ
약간 바보인줄 알았닿ㅎㅋ

import sys
import math
from itertools import combinations
sys.stdin=open("num1007input.txt")
T=int(sys.stdin.readline())
for _ in range(T):
    N=int(sys.stdin.readline())
    aPoints=[]
    bPoints=[]
    rules=[]
    for _ in range(N):
        a,b=map(int,sys.stdin.readline().split())
        aPoints.append(a)
        bPoints.append(b)
        rules.append((a,b))
    combi=list(combinations(rules, N//2))
    minuss=[]
    for i in combi:
        x1=0
        y1=0
        for j in i:
            x1+=j[0]
            y1+=j[1]
        final=math.sqrt((sum(aPoints)-2*x1)**2+(sum(bPoints)-2*y1)**2)
        minuss.append(final)
    reeee=min(minuss)

    print("%.8f" %reeee)

일단 이 문제는 저번 포스팅에 올렸던 부스트포스 알고리즘에 관한 문제이다.
모든 경우의 수를 다 판별해서 그 중 최소값을 찾는 알고리즘이다.
풀이는 생각보다 어렵지는 않다.
벡터의 덧셈은 요소끼리 나눠서 성분끼리 따로 계산하면 되는데,
절반을 골라서(combination) 모두 더한 값에서 2회 빼줘서 그 길이가 최소가 되는 값을 찾아주면 되었다.
모든 경우의 수를 다 계산해서 결과를 찾는 것 이므로 정답이 아닐 수 없다.
실행 속도의 문제가 있었지만, python3로 돌리지 않고 pypy3로 돌려보니 시간 초과가 뜨지 않았다.
pypy와 python의 차이점은 다음 포스트에 올릴 예정이다.
ㅇㅕ튼 열공

 

+2023.05.19.

지금은... 이거보단... 더 잘 짤 수 있을거같다...