[백준 알고리즘: python 3] #1007 - 벡터 매칭

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

 

1007번 문제는 벡터와 관련된 문제입니다. N 개의 점(N은 짝수)들이 주어지면, 2개의 점을 각각 연결하여 총 N/2개의 벡터 셋을 만들 때, 그 벡터들의 합의 길이의 최솟값을 구하는 문제입니다.

 

벡터들의 합의 길이의 최솟값! 이라고 했습니다. 이 때, 벡터의 합이 어떤 성질을 가질까에 대한 생각을 해볼 수 있겠네요. 예를 들어,

(x1, y1), (x2, y2), (x3, y3), (x4, y4) 이렇게 네 점이 주어져 있다고 생각해보면,

 

(x1, y1)에서 (x2, y2)를 향하는 벡터 v1,

(x3, y3)에서 (x4, y4)를 향하는 벡터 v2

 

를 생각해볼 수 있습니다. 그리고 각 벡터의 값은 다음과 같이 표현할 수 있습니다.

 

v1 = (x2-x1, y2-y1)

v2 = (x4-x3, y4-y3)

 

그리고 이 벡터들의 합은

 

v1 + v2 = (x2+x4 -x1-x3, y2+y4 -y1-y3)

 

가 되겠죠?

 

Hint!

즉, 벡터들의 끝 지점에 있는 점들을 모두 합한 것과, 시작 지점에 있는 점들을 모두 뺀 것이 N개의 점으로 만든 N/2개의 벡터들을 합하여 만든 벡터의 값과 같다는 겁니다. 색칠한 부분의 좌표값들을 보면, 만약 N개의 점이 주어져 있을 때도 N/2개의 벡터의 합을 나타낼 때도 그리 어렵지 않을 것을 알 수가 있습니다.

 

v1 + v2 + v3 + ... + vN/2 = (x2+x4+x6+...+xN -x1-x3-x5...-xN-1,y2+y4+y6+...+yN -y1-y3-y5...-yN-1)

 

그러면, 절반의 좌표는 더하고 절반의 좌표는 빼서 벡터들의 합을 구할 수 있다는 것이네요! 그러면 최소값은 어떻게 구할까요? 저도 이 지점에서 고민을 오래했는데, 다행히 문제를 보면 점의 수 N은 20까지만 주어진다고 해요. 양이 적은 것을 보면 전체 탐색 후에 최솟값을 구해도 된다고 생각했습니다.

 

만일 20개의 점이 주어졌을 때를 가정해봅시다. 이 중에 10개의 점을 고르는 경우의 수는 조합(Combination)의 경우의 수로 구할 수 있습니다. 그리고 파이썬에는 조합의 경우의 수를 각각 튜플로 반환해 주는 내장 함수(itertools.combinations(iterable, n))가 있습니다. 조합의 경우의 수를 코드로 짜려고 하셨던 분들에겐 그러지 않아도 된다고 말씀드리고 싶습니다.

 

그리고, 저는 코드에 빼야하는 절반의 점들의 좌표합을 처음 입력 단계에서 점의 좌표 전체를 받으면서 모두 더하고 그 값에 10개로 선정된 점들의 좌표 합을 빼서 구했습니다. 제 코드에서는 그러면 loop가 2개가 사라졌거든요!  그렇게 해도 위에서 색칠한 두 부분 역시 잘 계산이 됩니다. 코드를 보시게 되면 참고해주세요.

 

 

아래는 위와 같은 생각으로 작성해 풀이한 코드입니다.

 

import sys
import math
import itertools
# import random
T = int(sys.stdin.readline())
results = []

for _ in range(T):
    N = int(sys.stdin.readline())
    coords = []
    
    # 모든 좌표들의 총합
    x_total = 0
    y_total = 0
    for _ in range(N):
        x, y = map(int, sys.stdin.readline().split())
        x_total += x
        y_total += y
        coords.append([x, y])
    
    res = math.inf
    combinations = list(itertools.combinations(coords, int(N/2)))
    combinations_len_half = int(len(combinations) / 2)
    for sum_coord in combinations[:combinations_len_half]:
        sum_coord = list(sum_coord)

		# 더해야하는 좌표 총합
        x1_total = 0
        y1_total = 0
        for x1, y1 in sum_coord:
            x1_total += x1
            y1_total += y1
        
        # 빼야하는 좌표 총합(= 모든 좌표들의 총합 - 더해야하는 좌표 총합)
        x2_total = x_total - x1_total
        y2_total = y_total - y1_total
        
        res = min(res, math.sqrt((x1_total - x2_total) ** 2 + (y1_total - y2_total) ** 2))

    results.append(res)

for result in results:
    sys.stdout.write(str(result)+'\n')