백준 벡터 매칭(1007)

벡터 매칭

1. 힌트

1) $N$개의 점으로 이루어진 집합 $P$에서 임의의 서로 다른 두 점 $p,\ q$를 골랐을 때 $p$와 $q$를 끝점으로 하는 벡터는 $2$개가 있고, 각각 좌표 성분으로 표기하면 $(p_x - q_x,\ p_y-q_y)$ 혹은 $(q_x-p_x,\ q_y-p_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)$ 혹은 $(x_q-x_p,\ y_q-y_p)$가 됩니다
최적해를 찾기 위해 우리가 고른 $\frac{N}{2}$개의 벡터의 집합을 $V$라고 해보겠습니다. 벡터의 합은 결국 또 다른 새로운 벡터인데 이는 각각의 좌표 성분을 모두 더하면 만들어 낼 수 있습니다. 그 벡터를 $\vec{S}$라고 해 보겠습니다
$\vec{S} = (V[0]_x,V[0]_y)\ +\ (V[1]_x,V[1]_y)\ +\ ...$가 됩니다.

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

$V$의 원소 벡터들은 $(x_p - x_q,\ y_p-y_q)$ 혹은 $(x_q-x_p,\ y_q-y_p)$로 생각할 수 있는데, 연산의 순서가 상관이 없으므로 우리는 $N$개의 정점에서 $\frac{N}{2}$개의 음수를 고르면 $\vec{S}$를 만들어 낼 수 있다는 것을 알 수 있습니다.
또한 벡터의 성분이 주어져 있을 때 그 벡터의 크기는 $\sqrt{x^2+y^2}$으로 쉽게 구할 수 있습니다.

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}$개를 선택하는 경우를 모두 시도하므로 이 경우의 수는 최대 $20 \choose 10$ $=184756$ 이 됩니다. 하지만 모든 원소마다 선택 하느나 하지 않느냐로 재귀 호출하므로 $O(2^N)$이 됩니다.