백준 1007

문제 링크

문제 설명.

벡터 매칭 문제.

각각의 케이스 T에 대하여, 숫자 N과 N개의 x,y좌표가 주어진다.
(N은 짝수, 2<=N<=20.)
이때 서로 겹치지 않는 각각의 두 점들을 벡터로 만들었을 때 그 합의 길이의 최솟값들을 차례대로 출력하는 문제이다.

문제 풀이.

맨 처음에는 아이디어가 잘 떠오르지 않길레 일단 구현해보자 하고 initial code를 짜는데 시간을 좀 들여봤다.(당연히 시간 초과를 염두에 두고 짰고, 예상대로 시간초과가 나왔다.) 주어진 dot들을 하나하나 체크해서 모든 점이 벡터로 이어졌을 때 벡터들의 합의 최소길이를 return하는 방식의 코드를 짰다.

from sys import stdin

def calc_dist(x,y):
    return (x**2+y**2)**(1/2)

def calc_total(lst,start,TF_lst,x,y):
    # print('input :',lst,start,TF_lst,x,y)
    if start == -1:
        global dist
        # print('x,y =',x,y)
        dist = min(dist,calc_dist(x,y))
        return
    
    if dist == 0:
        return
    
    TF_lst[start] = True
    for i in range(start+1,len(lst)):
        if TF_lst[i] == False:
            TF_lst[i] = True
            z = -1
            try:
                z = TF_lst.index(False)
            except:
                pass
            
            x_new = x + (lst[start][0]-lst[i][0])
            y_new = y + (lst[start][1]-lst[i][1])
            calc_total(lst,z,TF_lst,x_new,y_new)
            
            x_new = x - (lst[start][0]-lst[i][0])
            y_new = y - (lst[start][1]-lst[i][1])
            calc_total(lst,z,TF_lst,x_new,y_new)
            
            TF_lst[i] = False
    
    TF_lst[start] = False
    return

cases = int(stdin.readline())
dist = 0
for _ in range(cases):
    dots = [list(map(int,stdin.readline().strip().split())) for _ in range(int(stdin.readline()))]
    
    dist = float('inf')
    calc_total(dots,0,[False for _ in range(len(dots))],0,0)
    
    print(dist)

코드를 다 짠후 몇몇 케이스를 돌려보면서 생각했을 때 벡터의 기본 개념으로부터 아이디어가 떠올라 새로운 코드를 짜게 되었다.

두 점 (x_1,y_1)과 (x_2,y_2)로부터 벡터가 만들어질 때 그 벡터의 방향과 크기를 나타내는 방식은 다음과 같다; <x_2-x_1,y_2-y_1>.
따라서 N개의 점을 모두 벡터로 만들었을 때 벡터의 시작점들과 도착점들이 무엇인지만 따져서 그 합의 최솟값을 계산하면 된다.

정답 코드.

from sys import stdin
from itertools import combinations

cases = int(stdin.readline())
dist = 0
for _ in range(cases):
    x_lst = []
    y_lst = []
    leng = int(stdin.readline())
    for _ in range(leng):
        x,y = map(int,stdin.readline().strip().split())
        x_lst.append(x)
        y_lst.append(y)
    dist = float('inf')
    
    for i in combinations(range(leng),leng//2):
        xs,ys = 0,0
        for j in range(leng):
            if j in i:
                xs += x_lst[j]
                ys += y_lst[j]
            else:
                xs -= x_lst[j]
                ys -= y_lst[j]
                
        dist = min(dist,xs**2+ys**2)
        
    print(dist**(1/2))

cf. pypy3로 통과를 했고, 좀 더 효율적으로 짠다면 python으로 통과가 가능할 것 같긴 하지만 길디 긴 initial code까지 작성했는데 개선까지 하기엔 귀찮아서 생략..(대부분 python으로 통과한 케이스가 pypy이고, 정말 극히 일부가 python으로 통과를 했던데 아마도 극한의 효율을 추구하며 통과를 하게 된 것이 아닐까 싶다.)