백준 1007 - 벡터 매칭

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

1007번: 벡터 매칭

---

문제해석

임의의 점이 N개 주어진다. 해당 N개의 점을 한 번씩 사용해서 만들 수 있는 벡터들의 합 중 최소값을 찾고, 길이를 구해야 한다.
점 (5, -3)에서 점 (2, 4)를 향하는 벡터는 다음과 같다. (2-5, 4+3) = (-3, 7)
또한 벡터 (-3, 7)과 벡터(2, -2)의 합은 다음과 같다. (-3 + 2, 7 -2) = (-1, 5)

또한 이렇게 만들어진 벡터의 길이를 구해야 한다.(점 (0, 0)에서 점 (-1, 5)까지의 거리를 구하면 된다.)

√(-1-0)^2 + (5-0)^2 = √26이 된다.

이렇게 구한 벡터합의 길이 중 최소값은 무엇인지 구하는 문제이다.

 

정리

점 (x0, y0)에서 점 (x1, y1)을 향하는 벡터는 (x1 - x0, y1 - y0)가 된다.

점 (x2, y2)에서 점 (x3, y3)을 향하는 벡터는 (x3 - x2, y3 - y2)가 된다.

이 벡터들의 합은 (x1 + x3 - x0 - x2, y1 + y3 - y0 - y2)이다.
결론적으로 점이 4개일 때 점 2개의 좌표는 더하고 2개의 좌표는 빼면 된다.
점이 6개이면? 3개의 좌표는 더하고, 3개의 좌표는 빼면 된다.
즉 N개의 점 중 N/2개의 좌표는 더하고 나머지 N/2개의 좌표는 빼면 된다.

 

접근방법

1. 모든 벡터들의 합을 구한다.
필자의 경우 벡터의 합을 구할 때 모든 좌표들의 합에서 뺄 좌표의 2배를 빼서 구했다.

점 (x0, y0)에서 점 (x1, y1)을 향하는 벡터와

점 (x2, y2)에서 점 (x3, y3)을 향하는 벡터의 합을 구할 때

즉, (x0 + x1 + x2 + x3, y0 + y1 + y2 + y3)에서 뺄 좌표인 (x0, y0)와 (x2, y2)를 2번 빼는 것이다.

(x0 + x1 + x2 + x3 - x0 - x0 - x2 -x2, y0 + y1+ y2 + y3 - y0 - y0 - y2 - y2)

= (x1 + x3 - x0 -x2, y1 + y3 - y0 - y2)이 된다.

 

2. 벡터들의 합을 구하면서 합의 최소값을 찾는다.

3. 마지막에는 이 합의 최소값의 제곱근을 구해서 출력한다.

 

모든 좌표를 탐색하기 위해 DFS를 사용했다.

---

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int totalX, totalY, target, vx, vy;
    static int coor[][]; //좌표 배열
    static double min;

		// 백준 1007 - 벡터 매칭
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) { //T회만큼 최소값을 구하는 로직 실행
            int n = Integer.parseInt(br.readLine());
            target = n / 2; // n의 절반, target만큼 좌표를 뺀다.
            coor = new int[n][2];
            totalX = 0;
            totalY = 0;
            min = Double.POSITIVE_INFINITY;

            for (int j = 0; j < n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
                coor[j] = new int[]{x + x, y + y}; //좌표를 기록하는데, 원래 좌표의 2배만큼 기록한다.
                totalX += x; //x좌표의 총합을 구한다.
                totalY += y; //y좌표의 총합을 구한다.
            }

			// 탐색을 시작할 index를 포함하여 요소의 개수가 target 이상인 경우에만 탐색을 시작한다.
            for (int j = 0; coor.length - j >= target; j++) {
                //탐색 시작 전 vx와 vy 초기화
                vx = totalX; //벡터 x의 합 저장
                vy = totalY; //벡터 y의 합 저장
                getMinVec(j, 1);
            }
            System.out.println(Math.sqrt(min));
        }
    }

    private static void getMinVec(int idx, int depth) {
        vx -= coor[idx][0]; //x좌표의 총합에서 원래 x의 2배만큼 빼서 벡터의 총합을 구한다.
        vy -= coor[idx][1]; //y좌표의 총합에서 원래 y의 2배만큼 빼서 벡터의 총합을 구한다.

        if (depth >= target) {
            min = Math.min((long)vx * vx + (long)vy * vy, min);
        }
        else {
            ++depth; // depth를 증가시킨다.
            // 탐색을 시작할 idx를 포함하여 요소의 개수가 앞으로 돌아야할 개수 이상인 경우에만 탐색을 시작한다.
            // target - depth + 1(위에서 ++depth를 했으나 아직 해당 depth에 대한 좌표는 빼지 않았으므로 +1을 하여 체크하지 않는다.)
            //더 쉽게 풀어서 쓰면 target - (depth - 1)이다.
            for (int i = idx + 1; coor.length - i >= target - depth + 1; i++) {
                getMinVec(i, depth); // 다음 좌표 탐색
            }
        }
        //탐색을 마친 경우 뺀만큼 다시 더해서 탐색을 계속할 수 있게 한다.
        vx += coor[idx][0];
        vy += coor[idx][1];
    }
}