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.
지금은... 이거보단... 더 잘 짤 수 있을거같다...
'Algorithm' 카테고리의 다른 글
[python] 백준 1002번 : 터렛 (0) | 2023.05.19 |
---|---|
[python] 백준 1004번 : 어린 왕자 (1) | 2023.05.19 |
[python] 백준 2563번: 색종이 (0) | 2023.01.15 |
[python] 백준 2581번: 소수 (2) | 2023.01.14 |
[python] 백준 2775번: 부녀회장이 될테야 (0) | 2023.01.13 |