7227. 사랑의 카운슬러 - d3

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Solution {
   static int[][] location;
   static boolean[] check;
   static int N;
   static long min;
    public static void main(String[] args) throws Exception{
      // TODO Auto-generated method stub

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      int T;
      T=Integer.parseInt(br.readLine());
      
      StringBuilder sb = new StringBuilder();
      StringTokenizer st;
      
      for(int test_case = 1; test_case <= T; test_case++)
      {
    	  N = Integer.parseInt(br.readLine());
    	  location = new int[N][2]; //지렁이 위치
    	  
    	  for(int i =0; i<N; i++) {
    		  st = new StringTokenizer(br.readLine()," ");
    		  location[i][0]=Integer.parseInt(st.nextToken());
    		  location[i][1]=Integer.parseInt(st.nextToken());
    	  }
    	  check = new boolean[N];
    	  
    	  min= Long.MAX_VALUE;
    	  make(0, 0);
    	  
    	  sb.append("#"+test_case+" "+min).append('\n');
      }
      System.out.print(sb);
   }
    public static void make(int cnt, int start) {
    	if(cnt == N/2) {
			min = Math.min(vectorPlus(),min);
			return;
		}
		for(int i=start; i<N; i++) {
			if(check[i] == false) {
				check[i] = true;
				make(cnt+1,i+1);
				check[i] = false;
			}
		}
	}
    static long vectorPlus() {
    	long dx = 0, dy = 0;
		for (int i=0; i <N; i++) {
			if (check[i] == true) {
				dx += location[i][0];
				dy += location[i][1];
			}
			else {
				dx -= location[i][0];
				dy -= location[i][1];
			}
		}
		return (dx*dx)+(dy*dy);
    }
}

 

지렁이 두마리씩 짝 짓기~

(내 짝도 ..😂)

 

난 벡터 성질을 몰랐다 ... 진짜 기억도 안나 옛날엔 알았나? ㅎ ㅎ ..

 

두 점 (x1,y1), (x2,y2) 가 있으면

(x1-x2, y1-x2) 

 

따라서 true 인 애가 (x1,y1)

false인 애가(x2,y2)

 

그러니깐 .. 조합(make())에선 (x1,y1)가 될 애들을 뽑아준거죠(방문)~

그래서 cnt == N/2 가 종료조건 !

 

true인 애를 더해주고 false 인 애를 빼주면

dx = x1-x2

dy = x2-y2

 

각 지렁이들이 움직인 벡터를 합하여 그 크기가 최소가 되도록 하는 문제이므로

 

저렇게 다 계산해준 다음(누적)

 

dx*dx + dy*dy 해주어서 벡터의 크기를 구하는 문제였다 .. (┬┬﹏┬┬)

 

근데 사실 아직도 내가 제대로 이해한건지 모르겠삼  맞나요? 내 머리 이해좀 해봐 .. 일하라고~