BOJ 1007 - 벡터 매칭

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 문제 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다. 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다. 테스트 케이... www.acmicpc.net 맨 처음 생각한 풀이법 : 20개의 점을 두 개씩 묶어서 계산한다. 그러나 이 방법은 O(20C2 * 18C2 * ... * 2C2)라는 무지막지한 시간복잡도가 생긴다. 다시 생각한 풀이법 : 고등학교 때 배운 수학지식을 이용. 이를...

원문링크 : BOJ 1007 - 벡터 매칭