벡터 매칭

[백준 1007] 벡터 매칭 C++

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 브루트 포스 1. 문제해결 아이디어 처음에 단순히 최대 20개의 점 중에서 2개씩 묶어 나가는 방법으로 풀려고 했다. 위 방법대로 하면 O(20 * 18 * ... * 4 * 2) 같은 끔찍한 시간복잡도가 나와 불가능함을 알 수 있었다. v1, v2 이라는 벡터가 있다고 가정해보자 v1 + v2 = = 이 된다. 여기서 알 수 있는점은 N개의 점 중에서, N/2개의 점은 시작점이 될 것이고, 나머지 N/2개의 점은 도착점이 되는 것을 알 수 있다. 따라..