망꼬누나의 개발 공부

[문제링크]

import java.util.*;

public class Main {
    static double answer;
    static int n, t;
    static int[] ax = new int[21]; //x좌표 배열
    static int[] ay = new int[21]; //y좌표 배열
    static boolean[] c = new boolean[21]; //조합 여부

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            n = sc.nextInt();
            answer = Double.MAX_VALUE;
            for (int j = 0; j < n; j++){
                ax[j] = sc.nextInt();
                ay[j] = sc.nextInt();
            }
            go(0, 0);
            System.out.printf("%.6f\n", answer); 
        }
    }

    static void go(int cnt, int index) {
        if (cnt == n / 2) {
            double x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                if (c[i]) {          //n/2개는 뺄셈
                    x -= ax[i];
                    y -= ay[i];
                }
                else {              //n/2개는 덧셈
                    x += ax[i];
                    y += ay[i];
                }
            }
            answer = Math.min(answer, Math.sqrt(x*x + y*y)); //최솟값 결정
            return;
        }
        if (index == n) return;
 
        go(cnt, index + 1);
        c[index] = true;
        go(cnt + 1, index + 1);
        c[index] = false;
    }
    
}

🔝조합을 활용한 코드이다.

이 문제는 벡터의 총합이 가장 작은 값을 출력하는 문제이다.

4개의 좌표가 (5,5), (5,-5), (-5,5), (-5,-5)인 경우, 최소 값은 0이다.

위의 사진을 보다시피 n개의 좌표가 주어졌을 때, n/2개의 좌표는 덧셈을, n/2개의 좌표는 뺄셈을 하는 것을 확인할 수 있다.

n의 최대값이 20이므로 n = 20이라 가정할 때, 20개 중 10개의 경우의 수이므로 20C10이 된다. 

즉, 184,756의 값으로 충분히 수행 가능한 시간이다.

최종적으로 조합 여부를 통해 선택된 경우(true)에는 뺄셈을, 선택되지 않은 경우(false)에는 덧셈을 하도록 한다.