1494. 사랑의 카운슬러

1494. 사랑의 카운슬러

개인적으로는 뭔가 이상한 문제라고 생각한다.

벡터를 구하는 방법에 대한 설명이 좀 더 필요한 문제라고 생각한다.

예를들어 A(6,0) B(3,3), C(-7,2), D(-4, -1) 이라 할때, 문제에서는 AB(3,-3) , CD(-3,3) 이고 두 벡터의 합은 (0,0) 이므로 답 0

이렇게 나오지만, AB(3,-3),DC(3,-3) 이라고 구하면 두 벡터의 합은 (6,-6) 이므로 답이 72가 되기 때문이다.

내가 이상한 해석을 하는건지는 모르겠지만 저런경우에 대한 명확한게 떨어지는 것 같다

아무튼 결국 출제자가 원하는 바는, 결국 벡터의 합의 제곱을 구하기 때문에 모든 쌍을 구하는 게 아니라는 점이다.

즉, 움직이는 절반의 지렁이만 정하고, 움직이는 지렁이와 움직이지 않는 지렁이를 아무렇게나 매치해도 결국 벡터값은 같다.

따라서 굉장한 시간절약으로 문제를 풀 수 있게 된다.

나는 이 문제를 모든 쌍에 대해서 구하고, 최소값을 찾는 방식으로 풀었는데, 내가 말한 오류? 때문에 제대로 된 답이 안나왔다.

그래도 평소에 생각하고 있었던, N개 중에서 2개씩 짝짓는 방법을 SLACK의 갓님들 덕분에 알게됐다.

N개에서 2개씩 고르려면 엄청난 중복이 발생하는데, 아주 작은 수부터 짝을 짓는다고 생각하고 풀면 되는 거였다.

(혹시 까먹을까 코드를 첨부해놔야겠다)

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
 
long long ans;
int n;
bool haveTeam[20];
void dfs(int pos,int num,vector<pair<long long, long long>> &warm)
{
    if (num == n/2)
    {
        long long sum = 0;
        long long x = 0;
        long long y = 0;
        for (int i = 0; i < n; i++)
        {
            if (haveTeam[i])
            {
                x += warm[i].first;
                y += warm[i].second;
            }
            else
            {
                x -= warm[i].first;
                y -= warm[i].second;
            }
        }
 
        sum = x*x + y*y;
 
        if (ans == -1)
        {
            ans = sum;
        }
        else if (ans > sum)
        {
            ans = sum;
        }
        return;
    }
 
    for (int i = pos+1; i < n; i++)
    {
        if (!haveTeam[i])
        {
            haveTeam[i] = true;
            dfs(i, num + 1, warm);
            haveTeam[i] = false;
        }
    }
 
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> n;
        vector<pair<long long, long long>> warm(n);
        ans = -1;
        memset(haveTeam, false, sizeof(haveTeam));
 
        for (int i = 0; i < n; i++)
        {
            cin >> warm[i].first >> warm[i].second;
        }
 
        dfs(-1,0,warm);
 
        cout <<"#"<<t<<" "<< ans << "\n";
    }
 
    
    return 0;
}

<코드:N개 중에서 2개를 고르는 방법>

void dfs(int pos)
{
    //짝이 n/2쌍 이루어졌을 
    if (num == n / 2)
    {
        return;
    }
 
    for (int i = pos + 1; i < n; i++)
    {
        //짝지어지지 않은 가장 작은 수 고르기
        if (!haveTeam[i])
        {
            haveTeam[i] = true;
            //짝지어지지 않은 가장 작은 수 고르기
            for (int j = 0; j < n; j++)
            {
                if (!haveTeam[j])
                {
                    //i 와 j 는 쌍을 이룬다.
                    haveTeam[j] = true;
                    team[i] = team[j] = num;
                    num += 1;
                    dfs(i);
                    num -= 1;
                    haveTeam[j] = false;
                }
            }
            haveTeam[i] = false;
            break;    //가장 작은 수 i를 찾고, 그 수와 다른 수 j를 매칭하는 모든 경우를 보는 거니까
                    //!haveTeam[i]가 되면 그 뒤에 있는 i는 볼 필요 없음.
        }
    }
 
}