[백준]1007 벡터 매칭

1007번: 벡터 매칭 (acmicpc.net)

1007번: 벡터 매칭

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

 

내풀이

벡터의 합의 길이의 최솟값을 구하라... 사실 문제랑 테케를 계속 보는데 도대체 왜 이 값이 정답인지? 잘 이해가 안되었다.

그래서 풀이를 보고 문제를 이해하고 나니 어려운 문제는 아니였다.

(집합 P에 있는 점들에서 모든 점들을 한번씩 사용해서 만들 벡터들의 합) 의 길이의 최솟값

즉 (x1,y1),(x2,y2),(x3,y3),(x4,y4)가 있을 때

V1<x2-x1, y2-y1> , V2<x4-x3,y4-y3>  로 벡터를 구성하면

V1 + V2  의 길이는 <x2+x4-x1-x3, y2+y4-y1-y3> 이 될 것이고 이의 길이는 벡터의 크기 구하는 공식을 사용하면 된다.

여기까지 보면 느낌이 오지 않는가?

주어진 점들로 벡터 모음을 만들면 2N개의 점이 주어질 때 N개의 점은 출발점이 될 것이고, N개의 점은 도착점이 될 것이다.

그리고 답은 < Sum(도착점의 x) - Sum(출발점의 x), Sum(도착점의 y) - Sum(출발점의 y) > 의 벡터 크기가 최소가 되는 경우이다.

고로 출발점과 도착점을 가르는 경우의 수 만큼 계산을 해보야한다 => 2nCn 의 경우의 수를 시도해보자

 

 public static double sol(){
        int M = N / 2;
        double min = Integer.MAX_VALUE;
	//비트마스킹을 통해 조합 구현하여 경우의 수 계산
        for (int i = 1; i < (1<<N); i++) {
            int endGroupX = 0;
            int endGroupY = 0;
            if (Integer.bitCount(i) == M) {
            	// 도착점을 골라 계산
                for (int j = 0; j < N; j++) {
                    if (((1 << j) & i) > 0) {
                        endGroupX += points[j][0];
                        endGroupY += points[j][1];
                    }
                }
                // 출발점은 전체 - 도착점들 
                int startGroupX = totalX - endGroupX;
                int startGroupY = totalY - endGroupY;

		// 벡터 크기값 구해가며 최소 찾는다
                double value = getVectorValue(startGroupX, startGroupY, endGroupX, endGroupY);
                if (min > value) {
                    min = value;
                }
            }
        }
        return min;
    }

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader input;
    static StringBuilder output = new StringBuilder();
    static String src = "2\n" +
            "4\n" +
            "5 5\n" +
            "5 -5\n" +
            "-5 5\n" +
            "-5 -5\n" +
            "2\n" +
            "-100000 -100000\n" +
            "100000 100000";

    static int T, N, points[][],totalX, totalY;

    public static void main(String[] args) throws IOException {

        input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        //풀이
        T = Integer.parseInt(input.readLine());
        for (int testcase = 1; testcase <= T; testcase++) {
            N = Integer.parseInt(input.readLine());
            points = new int[N][2];
            totalX = 0;
            totalY = 0;
            for (int i = 0; i < N; i++) {
                StringTokenizer str = new StringTokenizer(input.readLine());
                int x = Integer.parseInt(str.nextToken());
                int y = Integer.parseInt(str.nextToken());
                totalX += x;
                totalY += y;
                points[i][0] = x;
                points[i][1] = y;
            }
            // 점 (x1,y1), (x2,y2) 에서 벡터는 <x2-x1,y2-x1>
            // 모든 벡터의 합은 => 도착지 점들 좌표 - 출발지 점들 좌표
            // 출발지 와 도착지를 가르고 (20C10) 비교하는 방법으로 해결
            output.append(sol()).append("\n");
        }
        System.out.print(output);
    }
    public static double sol(){
        int M = N / 2;
        double min = Integer.MAX_VALUE;

        for (int i = 1; i < (1<<N); i++) {
            int endGroupX = 0;
            int endGroupY = 0;
            if (Integer.bitCount(i) == M) {
                for (int j = 0; j < N; j++) {
                    if (((1 << j) & i) > 0) {
                        endGroupX += points[j][0];
                        endGroupY += points[j][1];
                    }
                }
                int startGroupX = totalX - endGroupX;
                int startGroupY = totalY - endGroupY;

                double value = getVectorValue(startGroupX, startGroupY, endGroupX, endGroupY);
                //System.out.println(value);
                if (min > value) {
                    min = value;
                }
            }
        }
        return min;
    }

    public static double getVectorValue(int sX, int sY, int eX, int eY) {
        return Math.sqrt(Math.pow(eX - sX, 2) + Math.pow(eY - sY, 2));
    }
}