[SWEA] - 7227. 사랑의 카운슬러 (D3)

[문제]

오훈이에게는 지렁이 친구 N마리가 있다. 오훈이는 지렁이들을 위해 소개팅을 주선하고자 한다.
주선 방법은 임의의 지렁이 두 마리를 매칭시킨 후 한 지렁이에게 다른 지렁이가 있는 곳으로 가도록 하는 것이다.
이 때, 수학을 좋아하는 오훈이는 가능한 지렁이들이 움직인 벡터 합의 크기가 작기를 바란다.
지렁이들은 2차원 평면 안에서 꿈틀거리고 있는데,
지렁이들이 움직인 벡터를 나타내는 방법은 점 A 위에 있는 지렁이가 점 B 위에 있는 지렁이에게 갔다면,
그 벡터는 점 A에서 점 B를 가리키는 벡터가 된다.
벡터 V=(x, y)의 크기는 다음과 같이 정의하자.
│V│=│(x, y)│= x * x + y * y
모든 지렁이들을 매칭시키고 소개팅을 주선하되, 각 지렁이들이 움직인 벡터를 합하여 그 크기가 최소가 되도록 하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 정수 N(2 ≤ N ≤ 20, N은 짝수) 가 주어진다.
두 번째 줄 N개의 줄에는 지렁이들이 존재하는 점의 좌표가 주어진다.
모든 좌표 값은 절대값이 100,000보다 작거나 같은 정수다. 지렁이들은 모두 서로 다른 위치에 있다.

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
지렁이의 움직인 벡터의 합의 크기의 최소값을 출력하라.

문제 풀기

7227. 사랑의 카운슬러

---

[풀이]

• 두 마리의 지렁이끼리 매칭을 시켜줘야 하므로 조합을 이용하여 풀이
• 전체 지렁이 수의 절반까지 골랐다면 선택된 지렁이가 선택되지않은 지렁이의 방향으로 가는 것이므로
  백터의 합 = (선택된 지렁이들의 좌표 합) - (선택되지 않은 지렁이들의 좌표 합) 이 된다.

import java.util.Scanner;

class Solution {
	public static int n;
	public static long min;
	
	public static int[][] arr;
	public static boolean[] visit;
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			n = sc.nextInt();

			arr = new int[n][2];
			visit = new boolean[n];
			
			min = Long.MAX_VALUE;
			
			for(int i=0; i<n; i++) {
				arr[i][0] = sc.nextInt();
				arr[i][1] = sc.nextInt();
			}
			
			combination(0, 0);
			
			System.out.format("#%d %d\n", tc, min);
		}
	}
	
	public static void combination(int cnt, int start) {
		if(cnt == n/2) {
			long dx = 0;
			long dy = 0;
			for(int i=0; i<n; i++) {
				// 선택된 지렁이(출발지점)
				if(visit[i]) {
					dx += arr[i][0];
					dy += arr[i][1];
				}
				// 선택안된 지렁이(도착지점)
				else {
					dx -= arr[i][0];
					dy -= arr[i][1];
				}
			}
			
			long vector = (dx * dx) + (dy * dy);
			
			min = Math.min(min, vector);
			return;
		}
		
		for(int i=start; i<n; i++) {
			visit[i] = true;
			combination(cnt+1, i+1);
			visit[i] = false;
		}
	}
}