[BOJ][Python] 백준 1007번: 백터 매칭

1일 1PS 43일차!

📚 문제

---

골드 2

• 브루트 포스

• 벡터는 모두 [x1 - x2, y1 - y2] 꼴로 나타난다.
• 두 벡터의 합은 [x1 + x3 - x2 - x4, y1 + y3 - y2 - y4] 로 풀어낼 수 있다.
• 벡터의 크기를 구하기에 [x2 - x1, y2 - y1] 과 [x1 - x2, y1 - y2] 는 동일한 크기를 가지기에 조합의 절반만 검사하면 된다.

💡 풀이 과정

---

1. N/2 개의 벡터를 모두 원점에서 출발한다고 생각하자.
2. 모든 벡터의 합은 [(x1 + x3 + x5 + …) - (x2 + x4 + x6 + …)] 로 나타낼 수 있다.
3. combination 을 통해 조합을 만들어내고 각 조합에 따른 x, y 의 합을 계산해 거리를 구한다.

📌포인트

---

• combi = combi[:len(combi)//2 + 1]
  • 절반만 검사하고 싶다면 len(combi)//2 로 슬라이싱 해야한다.

💻 코드

---

import math
import sys
from itertools import combinations

T = int(input())

for _ in range(T):
    N = int(input())
    vectors = [list(map(int, input().split())) for _ in range(N)]

    total_x = total_y = 0
    for v in vectors:
        total_x += v[0]
        total_y += v[1]

    min_dis = sys.maxsize

    combi = list(combinations(vectors, N//2))
    combi = combi[:len(combi)//2 + 1]

    for com in combi:
        temp_x, temp_y = 0, 0
        for c in com:
            temp_x += c[0]
            temp_y += c[1]

        dis = math.sqrt((total_x - 2 * temp_x) ** 2 + (total_y - 2 * temp_y) ** 2)
        min_dis = min(min_dis, dis)

    print(min_dis)