[백준 1007번] 벡터 매칭

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

1007번: 벡터 매칭

 

재밌는 문제네요. 좌표평면 상의 벡터합 수식을 정리하면 결국 점들을 머리방향, 꼬리방향으로 양분해 처리하는 문제로 바뀝니다.

총 20개의 점들 중 10개를 선택하는 각각의 조합에 대해 벡터의 크기를 구해 최소값을 구합니다.

 

좋은 글이 있어 링크를 첨부합니다.

 

네로의 다락방님 블로그

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/*
백준 1007 벡터 매칭
https://www.acmicpc.net/problem/1007
 */
public class Main {

    static int T,N;
    static double INF = 9876543210d;
    static boolean[] isHead;
    static List<Point> points;
    public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//	BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
	T = Integer.parseInt(br.readLine());

	for (int testCase = 0; testCase < T; testCase++) {
	    N = Integer.parseInt(br.readLine());
	    isHead = new boolean[N];
	    points = new ArrayList<>();
	    for (int i = 0; i < N; i++) {
	        String[] pointInput = br.readLine().split(" ");
	        int x = Integer.parseInt(pointInput[0]);
	        int y = Integer.parseInt(pointInput[1]);
		points.add(new Point(x,y));
	    }

	    double ans = solve(0,1);
	    System.out.println(ans);
	}


    }

    private static double solve(int index, int count) {
	isHead[index] = true;

	if(count == N/2) {
	    double ret = getVectorSize();
	    isHead[index] = false;
            return ret;
	}

        double ret = INF;
	for (int i = index+1; i < N; i++) {
	    if(!isHead[i]) {
	        ret = Math.min(solve(i, count+1), ret);
	    	isHead[i] = false;
	    }
	}

	return ret;
    }

    private static double getVectorSize() {
        double totalX = 0;
	double totalY = 0;

	for (int i = 0; i < N; i++) {
	    if(isHead[i]) {
	        totalX += points.get(i).x;
	        totalY += points.get(i).y;
	    }else {
		totalX -= points.get(i).x;
		totalY -= points.get(i).y;
	    }
	}
        return Math.sqrt(totalX*totalX + totalY*totalY);
    }
}
class Point {
    int x,y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}