[백준] #1007 Python

백준 1007번 파이썬

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

아이디어

PyPy3에서 돌아간 코드(Python3에서는 시간초과 남)
벡터의 합의 길이의 최솟값 -> 의미의 정의가 가장 중요했던 것 같다.
벡터 a는 ax와 ay로 분할할 수 있습니다. 두 벡터 a와 b의 합은 a + b = (ax + bx, ay + by) 로 계산하게 된다. 여기서 ax와 bx는 좌표평면일 때에 head의 좌표에서 tail의 좌표를 뺀 값이다. 따라서 벡터의 합은 ((head에 해당하는 x의 값의 합 - tail에 해당하는 x의 값의 합) = x_ans, (head에 해당하는 y 값의 합 - tail에 해당하는 y 값의 합) = y_ans) 이다.

전체 좌표 중 절반을 head 배열, 나머지를 tail 배열로 나눈 모든 경우의 수를 살펴야 하기 때문에 combination을 사용했다. 또한, 나는 두 배열의 차를 알고 싶기 때문에 모든 경우의 수를 다 볼 필요가 없고 절반의 경우의 수만 보면 된다.

전체코드

import sys
from itertools import combinations
import math

input = sys.stdin.readline


# def comb(lst,n): #조합 구하는 알고리즘 -> 재귀함수 사용
# 	ret = []
# 	if n > len(lst): return ret
	
# 	if n == 1:
# 		for i in lst:
# 			ret.append([i])

# 	elif n>1:
# 		for i in range(len(lst)-n+1):
# 			for temp in comb(lst[i+1:],n-1):
# 				ret.append([lst[i]]+temp)

# 	return ret


N = int(input().rstrip())
for i in range(N):
    M = int(input())
    x_total, y_total = 0, 0
    coords = []
    for i in range(M):
        x, y = map(int, input().split())
        x_total += x
        y_total += y
        coords.append([x, y])
        
        comb = list(combinations(coords, M//2))
        comb_half_len = len(comb) // 2
        ans = float('inf')
        for part in comb[:comb_half_len]:

            x1_total, y1_total = 0, 0
            for x1, y1 in part:
                x1_total += x1
                y1_total += y1
        
            x2_total = x_total - x1_total
            y2_total = y_total - y1_total

            ans = min(ans, math.sqrt((x1_total - x2_total) **2 + (y1_total - y2_total)**2))

    print('{:.12f}'.format(ans))

느낀점

원래는 coords에 한번에 묶어서 보지 않고 x와 y배열을 따로 만들어서 계산해주었더니 오류가 계속 났었다,, 아마 조합의 경우의 수에서 for문을 돌 때 같이 보지 않아서 문제가 생긴 것 같다. 조합의 경우의 수를 볼 떄는 절반의 경우의 수만 봐도 될 때가 있음을 기억하자!!