[백준] Q1007 벡터 매칭 Java

https://www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

1. 문제 유형과 이해

완전 탐색

평면 상에 N 개의 점이 찍혀있고 그 점들의 집합을 집합 P라고 하자.

집합P의 벡터 매칭은 벡터의 집합인데, 

집합 P의 한점에서 시작해서 다른 점에서 끝나는 집합이고, P에 속하는 모든 점은 한번 씩 쓰여야한다.

벡터 매칭의 벡터의 합의 길이의 최소값을 구하시오.

 두 점 (a,b)와 (c,d)의 벡터는

(a-c, b-d)가 된다. 이러한 벡터들의 집합이 벡터 매칭이 된다.

이 벡터 매칭에서 이 벡터들끼리 합하여 나온 벡터의 합의 길이 최소 값을 구하면 된다.

즉, 시작점 N/2개와 끝점 N/2개로 이루어져 있기 때문에 우리는 N/2개를 선택해주면되는데, 이 때

문제 조건에서 N은 20보다 작거나 같은 자연수이므로 구할 수 있는 최대 가짓 수는 $_20C_10$로 충분히 가능하다.

 

2. 문제 접근 방법

주어진 N개의 점 중 끝점들을 빼주면된다.

N개의 점을 골라서 빼주면 되는데 이 때 

 1. N 개의 점을 고르기 -> 백준 N과 K 문제처럼 생각하면 된다.

   중복을 허용하지 않고 N개 중 N/2개를 고르기라고 생각하고 큰 구조를 짠다.

 2. 점을 빼주기

   더해가면서 해당 select되는 점을 빼주는 방식 한가지 또는

  미리 다 더해놓고 해당 select되는점을 2번 빼주면 한 번 빼준 것과 마찬가지인 방식 한가지.

   시간 상으로 미리 다 더해놓고 빼주는 것이 빠르다.

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

/**
 * @문제번호 : Q1007
 * @문제이름 : 벡터 매칭
 * @난이도 : GoldII
 * @date : 2022-02-12 오전 7:59
 * @author : pcrmcw0486
 * @문제이해
 * 평면상 N개의 점 그 점 집합을 P
 * P의 벡터 매칭은 벡터의 집합 벡터는 P의 한점에서 다른 점으로 끝나는 벡터의 집합
 * P에 속하는 모든 점은 한번씩 쓰여야한다.
 * 벡터 매칭에 있는 벡터 개수는 P점의 절반이다.
 * 벡터 매칭의 벡터 합 길이 최소값
 * @알고리즘
 * 모든 조합을 보는 것은 너무 많은 경우의 수이다.
 * 벡터 합의 길이가 최소가 되려면,
 * @접근방법

 */
public class Main {
    static class Vec{
        double x;
        double y;

        public Vec(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public double sum(){
            return Math.sqrt(x * x + y * y);
        }
    }
    static double ans;
    static int N;
    static Vec[] data;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while( T-- >0){
            ans =Double.MAX_VALUE;
            N = Integer.parseInt(br.readLine());
            data = new Vec[N];
            double sumX=0, sumY=0;
            for(int i =0;i<N;i++){
                st = new StringTokenizer(br.readLine());
                data[i] = new Vec(Double.parseDouble(st.nextToken()), Double.parseDouble(st.nextToken()));
                sumX += data[i].x;
                sumY += data[i].y;
            }
            solution(0, 0, new Vec(sumX, sumY));
            sb.append(ans).append('\n');
        }
        System.out.println(sb);
    }

    public static void solution(int depth, int idx, Vec prev){
        if(depth == N/2){
            //N/2개를 이미 선택하여 뺏음
//            for(int i =idx;i<N;i++){
//                prev.x += data[i].x;
//                prev.y += data[i].y;
//            }
            ans = Math.min(ans, prev.sum());
            return;
        }
        for(int i= idx;i<N;i++){
            //select하는 경우
            solution(depth + 1, i+1, new Vec(prev.x -2*data[i].x, prev.y-2*data[i].y));
         
         //합을 따로 구하지 않는다면 현재 값을 빼보고 구해본뒤
         // 이후 더해서 다음 값을 확인한다.
         // 대신 이 방법이면 10개를 고른 후 나머지에 대하여 다시 다 더해줘야한다.
         // 이러한 문제 때문에 미리 다 더해놓고 빼주는 것이 더욱 빠르다.
         //solution(depth + 1, i+1, new Vec(prev.x -data[i].x, prev.y-data[i].y));
            // prev.x += data[i].x ;
          //  prev.y += data[i].y ;
            //select하고 나서 다음거 보기전에 자신을 더해줌 및 원상복귀
        }
    }
}