[SWEA] 1494. 사랑의 카운슬러

1494. 사랑의 카운슬러

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b_WPaAEIBBASw&categoryId=AV2b_WPaAEIBBASw&categoryType=CODE&problemTitle=%EC%82%AC%EB%9E%91%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

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

//210208

public class Solution_D4_1494_사랑의카운슬러 {

	static int N; 
	static int[][] map;
	static long min;
	static boolean[] isSelected;

	static void combination(int cnt, int start) {
		if (cnt == N/2) { // 백터 계산

			long[] v1 = {0, 0};
			long[] v2 = {0, 0};
			
			for(int i=0; i<N; i++) {
				if(isSelected[i]) {
					v1[0] += map[i][0]; // x좌표
					v1[1] += map[i][1]; // y좌표
				} else {
					v2[0] += map[i][0]; // x좌표
					v2[1] += map[i][1]; // y좌표
				}
			}
			
			long vX = v1[0] - v2[0];
			long vY = v1[1] - v2[1];
			long v = vX * vX + vY * vY;
			min = Math.min(min, v);

			return; 
		}
		
		for(int i=start; i<N; i++) {
			 if (isSelected[i]) continue;
			 isSelected[i] = true;
			 combination(cnt+1, i+1);
			 isSelected[i] = false;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][2];
			isSelected = new boolean[N];

			min = Long.MAX_VALUE; // 최대값 초기화를 이렇게 하는구나
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				map[i][0] = Integer.parseInt(st.nextToken()); // x 좌표 
				map[i][1] = Integer.parseInt(st.nextToken()); // y 좌표 
			}
			
			combination(0, 0);
			System.out.println("#" + tc + " "+ min);
			
		}

		br.close();
	}

}

 

오래 걸렸던 문제..

1. A좌표->B좌표 이동과 B좌표->A좌표 이동의 경우 다른 경우로 세야 한다고 생각했다. 그러나 어차피 벡터값을 다 더한 후 제곱하기 때문에 순서는 상관업삳. 따라서 순열이 아닌 조합으로 풀었다.

2. 제일 고민스러웠던 부분!!! 
   N마리의 지렁이중 두 마리를 뽑고, 남은 지렁이 중 다시 두마리를 뽑고,,
   nCr * n-2Cr-2 * n-4Cr-4 .. 이 되어야 한다고 생각해서 재귀로 조합을 어떻게 돌리지 싶었다.
   그러나 두마리씩 뽑은 후, 두 마리 사이의 벡터값을 구하기 위해 A좌표 - B 좌표 = 벡터값을 구한 다음. 벡터값을 더하기 때문에!!!
   절반은 뽑고 절반은 뽑지 않은 상태에서 각각 더해서 빼주어도 된다!!

3. 조합은 반복문 돌릴 때 i가 0이 아니라 start부터 시작한다는 거 헷갈리지 말자 ㄷㄷ