[Java] SWEA 7227번 사랑의 카운슬러

SW Expert Academy

---

풀이

각 좌표를 입력받고 두마리의 지렁이끼리 매칭되야하므로 조합을 사용하였습니다.

기저조건으로 전체 지렁이의 절반이 선택되면 선택된 지렁이들이 선택이 안된 지렁이들 방향으로 가게 되므로 선택된 지렁이들의 좌표는 더해주고 선택이 안된 지렁이들을 빼주어주면 벡터의 합을 구할 수 있습니다.

이때, 정답의 값은 int의 가장 큰 값을 초과할 수 있기 때문에 long형으로 처리하였고 이를 이용해서 벡터의 크기를 구하여 최소가 되는 값을 갱신하여 해결하였습니다.

---

코드

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

public class Solution {
	public static int N;
	public static long answer;
	public static int[] number;
	public static int[][] earthworms;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			answer = Long.MAX_VALUE;
			
			N = Integer.parseInt(br.readLine());
			
			earthworms = new int[N][2];
			number = new int[N];
			
			for (int i = 0; i < N; ++i) {
				st = new StringTokenizer(br.readLine(), " ");
				
				earthworms[i][0] = Integer.parseInt(st.nextToken());
				earthworms[i][1] = Integer.parseInt(st.nextToken());
			}
			
			combination(0, 0);
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		System.out.println(sb);
	}
	
	public static void combination(int cnt, int start) {
		if (cnt == N / 2) {
			long dx = 0, dy = 0;
			for (int i = 0; i < N; ++i) {
				if (number[i] > 0) {
					dx += earthworms[i][0];
					dy += earthworms[i][1];
				}
				else {
					dx -= earthworms[i][0];
					dy -= earthworms[i][1];
				}
			}
			long vectorSize = (dx * dx) + (dy * dy);
			
			answer = (answer > vectorSize) ? vectorSize : answer;
			return;
		}
		
		for (int i = start; i < N; ++i) {
			number[i] = 1;
			combination(cnt + 1, i + 1);
			number[i] = 0;
		}
	}
}

---

pyo7410/Algorithm