백준 1007 벡터 매칭

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1007

풀이

난이도 : Gold II

이 문제는 짝수 개의 좌표가 주어지면 그 중 절반을 시작점으로 잡고 남은 절반은 끝점으로 잡아 벡터를 만들어주고 그 벡터들의 합의 최솟값을 구하는 문제이다.

문제 풀이에서 핵심은 (끝점들의 x, y값들의 합 - 시작점들의 x, y값들의 합) 으로 한번에 벡터들의 합의 최솟값을 구하는 것이다. 따라서 시작점들을 뽑아 미리 x, y좌표들의 합을 구해놓고 계산만 진행하면 문제를 풀 수 있다.

조합을 이용하여 주어진 좌표 중 절반을 뽑아 시작점으로 잡았고, 처음 좌표들을 입력받을 때 x, y 좌표들을 모두 합한 값들을 저장하여 (총합 - 시작점들의 합) 으로 끝점들을 바로 구하였다.
python에는 combinations라는 함수가 있어 해당 함수를 사용하였다.

코드

    from itertools import combinations
    import sys

    input = sys.stdin.readline
    t = int(input())

    results = []
    for _ in range(t):
        n = int(input())
        graph = []

        total_x = 0
        total_y = 0

        for _ in range(n):
            x, y = map(int, input().split())
            graph.append([x, y])
            total_x = total_x + x
            total_y = total_y + y

        vertex = list(combinations(graph, n//2))
        result = int(1e9)

        for ve in vertex:
            x1, y1 = 0, 0
            for v in ve:
                x1 = x1 + v[0]
                y1 = y1 + v[1]

            x2 = total_x - x1
            y2 = total_y - y1
            result = min(result, ((x1-x2)**2 + (y1-y2)**2) ** 0.5)

        results.append(result)

    for r in results:
        print(r)