BOJ#1007 Vector Matching

* 문제

https://www.acmicpc.net/problem/1007

* 풀이

평면 상에 N개의 점이 찍혀있다. (N은 짝수)

N개의 점을 이용해서 벡터를 만든다.

벡터는 당연히 N/2개 나올 것이다.

문제를 자세히 보니, N개 점들의 좌표가 주어지고 평면벡터이다.

평면 상에 2개의 점 A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4)가 주어졌고

임의의 벡터를 구성했다고 가정해보자.

2개의 임의의 벡터이다.

AB = (x1-x2, y1-y2)

CD = (x3-x4, y3-y4)

위 2개의 벡터의 합은 아래와 같다.

AD+CD = (x1+x3-(x2+x4), y1+y3-(y2+y4))

위 벡터의 크기는

Math.sqrt((x1+x3-(x2+x4))^2, (y1+y3-(y2+y4))^2)

∴ 문제의 목표는 위 값의 최소값을 구하는 것이다.

결국 N개의 점에서 N/2개의 점을 뽑아야 한다.

왜냐하면 N/2개의 점은 +값을 갖고, 나머지 N/2개의 점은 -값을 갖기 때문이다.

따라서 N개의 점에서 N/2개의 점을 뽑는 모든 경우의 수에서 min값을 계속 갱신해야 한다.

이것을 풀기 위해 조합(Combination)을 이용해보자.

- 조합의 구현은 아래 링크를 참조해 봅시다.

- http://stack07142.tistory.com/25

public class Main { static double min = Double.MAX_VALUE; public static void main(String[] args) throws IOException { ...... // 테스트 케이스 Loop for (int t = 0; t < T; t++) { N = Integer.parseInt(br.readLine()); p = new Point[N]; // 배열 p의 Index 배열 pIterator = new int[N / 2]; min = Double.MAX_VALUE; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); p[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); } ...... // N개의 Point 중 N/2개의 Point를 뽑는다. combination(pIterator, 0, N, N / 2, 0, p); System.out.printf("%.6f\n",min); } } private static void combination(int[] arr, int index, int n, int k, int target, Point[] p) { if (k == 0) { min = calculateMin(arr, index, p); } else if (n == target) { return; } else { arr[index] = target; combination(arr, index + 1, n, k - 1, target + 1, p); combination(arr, index, n, k, target + 1, p); } } private static double calculateMin(int[] arr, int length, Point[] p) { double sumX = 0; double sumY = 0; double vectorLength = 0; for (int i = 0; i < p.length; i++) { sumX += p[i].x; sumY += p[i].y; } for (int i = 0; i < length; i++) { sumX -= (p[arr[i]].x) * 2; sumY -= (p[arr[i]].y) * 2; } vectorLength = Math.sqrt((sumX * sumX + sumY * sumY)); if (vectorLength < min) { min = vectorLength; } return min; }

각각의 경우가 추출될 때마다 벡터의 크기를 계산하여 계속 최소값을 갱신하면 된다.

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231007_VectorMatching