[백준] 1007 - 벡터 매칭

[문제링크]

1007번: 벡터 매칭

 

0. 모든 경우의 수에 대해 계산하는 브루트-포스 방식

 

1. 벡터는 두 점 A, B가 있을때 A-B / B-A 같은 식으로 만들 수 있다

  - 한 점은 +, 한 점은 - 하게 된다

 

2. 즉, 2N개의 점으로 N개의 벡터를 만들었을때 그 벡터들의 합은 N개의 점을 +, 나머지 N개는 - 한 값이다

 

3. 점이 최대 20개인데, 20개 중 10개를 뽑는 조합의 경우의 수 ₂₀C₁₀은 184756으로 산술 시간안에 충분히 해결 가능하다

 

4. 10개의 점을 선택해 더하고, 선택되지 않은 10개의 점을 빼는 식으로도 결과를 구할 수 있지만,

  - 산술 연산의 횟수를 줄이기 위해 모든 수를 더해두고, 10개의 점을 선택해 2번씩 빼준다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			N = pint(br.readLine());
			isC=new boolean[N];
			point= new int[N][2];
			int sumx=0,sumy=0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				point[i][0]=pint(st.nextToken());
				point[i][1]= pint(st.nextToken());
				sumx+=point[i][0];
				sumy+=point[i][1];
			}
			
			ans=Double.MAX_VALUE;
			rec(0,0, sumx, sumy);
			sb.append(ans).append("\n");
		}
		System.out.println(sb);
		
	}
	static double ans;
	static int N;
	static boolean[] isC;
	static int[][]point;
	
	static void rec(int cnt, int prev, int x, int y) {
		if(cnt==N/2) {
			ans = Math.min(ans, Math.sqrt((double)x*x + (double)y*y) );
			return;
		}
		for (int i = prev; i < N; i++)
			rec(cnt+1, i+1, x-2*point[i][0], y-2*point[i][1]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면