백준 1007 (벡터 매칭)

백준 1007 (벡터 매칭)

문제 링크

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

문제 접근

반갑습니다. 평면 상에 N개의 점이 주어지고, 점들을 집합 P라고 하겠습니다. 벡터 매칭은 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터들의 집합입니다. 또 P에 존재하는 점들은 한 번씩만 쓰여야 합니다. 벡터 매칭에 있는 벡터의 수는 P에 있는 원소의 절반입니다. 벡터 매칭에 존재하는 벡터들의 합의 길이의 최솟값을 구하는 문제입니다.

처음엔, 기하학 알고리즘을 사용한 많은 조건 분기 문제로 생각했습니다.

N개의 점 중, 초기 점을 두 개 고르고 벡터로 만들고, 이 벡터의 크기를 줄여가는 형식으로 생각을 했지만, 이는 최적의 해를 보장하지 못하기에, 브루트포스 문제로 판단하고 구현하였습니다.

처음, N개의 점 중 2개를 고르고,