[백준] 1007 - 벡터 매칭 🔀 (Python) / 골드 2 / 브루트포스

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 첫 줄에 테스트 케이스 T가 주어지고, 각 테스트 케이스에 대해 점의 개수 N이 주어집니다. 다음 N개의 줄에 x, y 좌표가 주어집니다. N은 항상 짝수입니다. 좌표 평면에 N개의 점이 있을 때, 모든 점을 사용해서 벡터를 N/2개 만들 때 벡터의 합이 최소가 될 때 최솟값을 출력해야 합니다.

1) 예제 입출력❄️

예제 입출력

첫 번째 예시는 4개의 점에 의해 정사각형이 만들어지기 때문에, 서로 반대방향의 벡터를 가로나 세로로 만들면 합했을 때 최솟값 0이 나오며, 두 번째 예시는 두 점이기 때문에 두 점에 의한 벡터의 길이가 곧 벡터의 합이 되어 길이를 출력하면 됩니다.

 

2. 핵심 논리☢️

핵심 논리

먼저, 저는 이 문제를 풀기 위해 벡터의 개념부터 알아보았습니다. 벡터는 한 점(X2)에서 다른 점(X1)으로 가는 화살표로 표현될 수 있습니다. X2의 좌표에서 X1의 좌표를 뺌으로써 하나의 벡터를 표현할 수 있습니다. 그리고 두 벡터의 합은 각각 x좌표와 y좌표의 합으로 표현할 수 있습니다. 즉, 여러 벡터가 있을 때, 벡터들의 합 벡터는 모든 x좌표의 합과 모든 y좌표의 합으로 표현될 수 있습니다. 

 이 문제의 핵심은 주어진 정점 N개에 대해 절반의 정점 N/2 개를 선택하면, 해당 점들을 끝점으로 하고, 나머지 선택되지 않은 N/2개의 점들을 시작점으로 하는 벡터들이 생기고, 모든 경우의 수에 대해 합벡터는 항상 1개 유일하다는 것입니다. 왜냐하면, 끝점과 시작점을 뺀 좌표들에 대해 모든 x좌표의 합과 모든 y 좌표의 합은 항상 일정할 것이기 때문입니다. 

 

3. 풀이 코드✅

1) 코드

import sys, itertools
input=sys.stdin.readline
T=int(input())
for _ in range(T):
    N=int(input()) # 점의 개수
    points = [] # 좌표의 리스트
    total_x,total_y = 0,0

    for _ in range(N):
        x,y = map(int,input().split())
        total_x +=x ; total_y += y # 모든 x의 합과 y의 합 저장
        points.append((x,y))

    comb = list(itertools.combinations(points, N//2))
    ans=3e5
    
    for c in comb[:len(comb)//2]: # len(comb)는 항상 짝수
        x1,y1 = 0,0
        for x,y in c:
            x1 += x ; y1 += y
        x2,y2 = total_x-x1,total_y-y1 # x와 y를 x1,y1과 x2,y2 두 그룹으로 절반 나누기
        
        hab_vector = ((x2-x1)**2 + (y2-y1)**2)**(0.5) # 절반 나눈 두 그룹간의 합벡터
        ans=min(ans,hab_vector)
    print(ans)

벡터의 합은 결국 두 벡터 간의 x좌표 합, y 좌표합으로 결합 법칙이 성립됩니다. 그러므로, 전체 정점에서 절반을 선택하면 자연스럽게 그 점들을 끝점으로 하는 벡터들의 합이 결정됩니다. 그러면 절반을 선택하는 모든 경우의 수가 곧, 모든 벡터들의 합의 경우의 수가 됩니다. 주어진, 정점에서 절반을 선택하는 모든 조합은 comb에 저장합니다. 그리고 for문에서 N의 개수는 항상 짝수이고, 여기서 Combination을 하면 항상 짝수가 보장됩니다. 그래서 len(comb)//2가 정수가 보장되며, comb에 대해 절반을 선택하면, 나머지 절반은 자동으로 선택되기 때문에 len(comb)//2 개수만큼만의 경우의 수만 봐도 모든 경우를 다 고려한 것입니다.

 ans는 첫 예시의 2번째 테스트 케이스에서 최대치가 약 28만으로 나왔으므로, max값을 30만으로 잡아두었습니다. 핵심은 정점들의 그룹에 대해 절반을 선택해서, 한쪽은 x1, y1으로 다른 쪽은 x2, y2로 좌표들을 모두 더한 뒤에 (x2-x1, y2-y1)이라는 합 벡터의 길이를 출력하면 됩니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1007_%EB%B2%A1%ED%84%B0_%EB%A7%A4%EC%B9%AD.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/