[BOJ] 1007 벡터 매칭 (C/C++)

1007번: 벡터 매칭

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10^-6까지 허용한다.

---

빡 수학 문제였다. 벡터랑 멀어진 지 너무 오래돼서 풀이 방법이 바로 생각이 안 났다. 벡터 성질만 제대로 알고 있다면 그렇게 어렵지 않은 문제였다. 이 문제는 오히려 고등학생 때 더 쉽게 풀었을 것 같다.

 

어차피 벡터이므로 N개 중에서 절반을 시작점으로 정하면 그 시작점이 각각 어떤 점 향하던 벡터 합은 같게된다. 따라서 DFS를 사용한 조합으로 N개 중에서 절반을 시작점으로 정한다. 그리고 시작점을 모두 고르면 고른 시작점으로 벡터 합을 구한다. 그러고 나서 크기만 구해주면 된다. 

 

중간에 sqrt 안에 계산하는 인자를 그냥 int로 사용했었다. 다른 입력은 잘되는데 특정 케이스만 안되길래 변수 타입의 문제인가 싶어서 double로 타입 캐스트를 해줬더니 답이 제대로 나오는 것을 볼 수 있었다. 계산할 때, 특히 곱하기는 변수의 범위를 넘어서는지 확인을 잘하고 넘어가자.

 

 

후기)

고등학교로 돌아간 것 같다. 고졸이 5년전인데...