백준 1007번 | 벡터 매칭 - python

https://www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

---

이번 문제의 경우에는 조합을 이용하여 문제를 풀려고 했으나, 20개의 값을 조합 형태로 표현하다보니 시간 초과가 발생하는 문제점이 있었다.

이를 해결하고자 다른 블로그를 찾아본 결과, 10개만 선택하여 그 값을 뺴주는 방식을 활용하면 시간복잡도가 확실하게 줄어든다는 것을 알게 되었다.

 

그래서 총합을 구한 뒤, 조합을 통해 얻은 좌표의 총합을 빼주는 방식으로 최솟값을 구해나가니 문제가 해결되었다.

 

import sys
from itertools import combinations

input = sys.stdin.readline

for _ in range(int(input())):
    answer = float('inf')
    n = int(input())
    graphs = [list(map(int, input().split())) for _ in range(n)]
    # 입력 받은 모든 좌표의 함을 x축, y축으로 해서 다 더해준다.
    x, y = map(sum, zip(*graphs))
    # 20C10의 시간 복잡도를 이용하여 10개의 좌표를 선택한다.
    # 선택하는 것이기 때문에 permutations이 아닌 combinations가 가능
    for combi in combinations(graphs, n // 2):
        # 선택한 좌표읜 x, y 합을 모두 구해준다.
        tmp_x, tmp_y = map(sum, zip(*combi))
        # 원래 값에는 모든 좌표가 더해져 있으니 선택한 좌표의 합을 2배한 뒤, 빼주고
        # 대각선의 스칼라 값을 구한다.
        # 구한 값을 answer와 비교하여 작은 값을 저장
        answer = min(answer, pow((x - 2 * tmp_x) ** 2 + (y - 2 * tmp_y) ** 2, .5))
    print(answer)