Sw Expert Academy 1494 사랑의 카운슬러 - C++

 

지렁이가 이동하는 총스칼라가 최소가 되게 하면 됩니다.

벡터의 크기는 편의상 루트를 없앤 x^2 + y^2로 계산합니다.

 

지렁이는 최대 20마리까지 존재하며 짝수입니다.

모든 좌표값은 -10만 <= x, y <= 10만입니다.

 

벡터가 제곱이기 때문에 10^10까지 거리가 멀 수 있기 때문에

integer로 풀 수 없고 long long으로 풀어야 합니다.

 

DFS로 무작정 풀 수도 있겠지만

가능한 경우의 수가 상당히 많습니다.

nC2 * n-2C2 *... 2C2가 되니 N이 늘어날수록

기하급수적으로 늘어나겠군요.

 

여기서 문제의 함정을 살펴봅시다.

 

각 지렁이들이 움직인 벡터 크기의 합이 아니라

각 지렁이들이 움직인 벡터의 합의 크기가 최소가 돼야 합니다.

 

즉 움직인 벡터합을 먼저 구해야 하는 문제입니다.

 

여기서 벡터의 성질을 이용해 보겠습니다.보겠습니다.

네.. 좀 대충 그렸지만 그러려니 합시다..

 

여기서 a 지렁이가 b로 간다고 하고, 그 벡터를 c로 둡시다.

그럼 a->b 벡터는 벡터의 성질을 이용하면 다음과 같습니다.

 

        →   → →

         c = b - a

 

기하와 벡터를 배우셨다면 아시겠죠?

a -> c 벡터를 더하면 b 벡터이니, c 벡터는 b 벡터 - a 벡터입니다.

 

고로 두 점 사이의 거리는 (4,1) - (1,3) = (3, -2)이고,

(0,0)과 (3,-2)의 거리는 3^2 + (-2)^2 = 13입니다.

 

다만, 다른 지렁이 벡터들도 모두 합한 후 

거리를 구해주어야 합니다.

 

여기서 가장 가까운 지렁이로 가야 한다는 조건 때문에

가장 가까운 지렁이를 찾는 과정을 넣으시면

시간초과가 날 확률이 높습니다.

 

벡터의 합을 구하는 것이고,

벡터의 합은 완전히 더하기 빼기로만 이루어져 있으므로

자연스럽게 결합법칙과 교환법칙이 성립됩니다.

 

즉, (1,2) (3,4) (7,8) (-2,5) 4마리가 있다고 했을 때,

누가 누가 더 가깝나를 찾기보다는

(1,2) (3,4)가 가만히 있다고 두고

(7,8) (-2,5)가 움직인다고 생각해 보면,

 

(1,2) - (7,8) + (3,4) - (-2,5)이고 결합법칙과 교환법칙이 성립하므로

((1,2) + (3,4)) - ((7,8) - (-2,5)) 가 성립하고

이는 가만히 있는 지렁이들을 먼저 고르면

벡터 합의 크기는 항상 일정하다는 것을 알 수 있습니다.

 

즉, 가만히 있는 지렁이를 반( N/2 )만큼 고르고,

고른 지렁이의 좌표는 더하고 움직이는 지렁이의 좌표를 뺀 후

제곱씩 하면 벡터 합의 크기를 구할 수 있습니다.

 

#include <stdio.h>
#include <string.h>
 
int t, n;
int worm_y[21];
int worm_x[21];
unsigned long long Max = 0;
int matched[21];
 
unsigned long long vectorSize(int y, int x) {
    return (unsigned long long)y * y +(unsigned long long) x *x;
}
 
void match(int num,int idx) {
    if (num == n / 2) {
        int y = 0, x = 0;
        for (int i = 0; i < n; i++) {
            if (matched[i]) {
                y += worm_y[i];
                x += worm_x[i];
            }
            else {
                y -= worm_y[i];
                x -= worm_x[i];
            }
        }
        if (Max > vectorSize(y, x)) Max = vectorSize(y, x);
        return;
    }
    for (int i = idx; i < n; i++) {
        matched[i] = 1;
        match(num + 1, i + 1);
        matched[i] = 0;
    }
}
 
unsigned long long solve() {
    Max = 80000000000+2;
    match(0,0);
    return Max;
}
 
int main() {
    scanf("%d", &t);
    for (int loop = 1; loop <= t; loop++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &worm_y[i], &worm_x[i]);
        }
 
        unsigned long long ans = solve();
        printf("#%d %llu\n", loop, ans);
    }
    return 0;
}