백준 벡터 매칭(1007)

벡터 매칭

1. 힌트

1) $N$개의 점으로 이루어진 집합 $P$에서 임의의 서로 다른 두 점 $p,\ q$를 골랐을 때 $p$와 $q$를 끝점으로 하는 벡터는 $2$개가 있고, 각각 좌표 성분으로 표기하면 $(p_x - q_x,\ p_y-q_y)$

2) 벡터의 합 연산은 좌표 성분으로 나타냈을 때 각각의 좌표 값을 더한 값이 됩니다. 또한 교환 법칙이 성립합니다.

3) 어차피 모든 점을 선택해야하므로 $N$개의 좌표 성분을 모두 더하되, 그 중에서 $\frac{N}{2}$

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

무식한 방법으로 생각하면 $N$개에서 $2$개의 점의 순서쌍을 $\frac{N}{2}$

2) 문제를 분해할 수 있을까?

$N$개의 점으로 이루어진 집합 $P$에서 임의의 서로 다른 두 점 $p,\ q$를 골랐을 때 $p$와 $q$를 끝점으로 하는 벡터는 $2$개가 있고, 각각 좌표 성분으로 표기하면 $(x_p - x_q,\ y_p-y_q)$

3) 문제를 단순화할 수 없을까?

$V$의 원소 벡터들은 $(x_p - x_q,\ y_p-y_q)$

3. 구현

public class Main {
	static int N;
	static Pair[] P;
	static boolean[] picked;
	
	// P[here, N)에서 k개를 고르는 경우 모두 시도
	static double bfc(int here, int k) {
		if (here == N) {
			if (k != 0) return Double.MAX_VALUE;
			long y = 0; long x = 0;
			for (int i = 0; i < N; i++) {
				if (picked[i]) { y -= P[i].y; x -= P[i].x; }
				else { y += P[i].y; x += P[i].x; }
			}
			return Math.sqrt(y * y + x * x);
		}
		double min = bfc(here + 1, k);
		picked[here] = true;
		min = Math.min(min, bfc(here + 1, k - 1));
		picked[here] = false;
		return min;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			N = Integer.parseInt(br.readLine());
			P = new Pair[N];
			picked = new boolean[N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				P[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			bw.append(bfc(0, N / 2)).append("\n");
		}
		System.out.print(bw);
	}

}
class Pair { 
	int y, x;
	Pair(int y, int x)  { this.y = y; this.x = x; }
}

1) 시간 복잡도

$N$개에서 $\frac{N}{2}$