백준 1007

이 문제는 특정한 점들을 두 개의 집합으로 나눌 때, 두 집합 간의 거리의 최소값을 구하는 문제입니다.
주어진 점들을 두 개의 집합으로 나누는 모든 경우를 구하고, 각 경우에서 두 집합 간의 거리를 구하여 그 중 최소값을 찾으면 됩니다.
하지만 이 방법은 시간 복잡도가 매우 크기 때문에 적용할 수 없습니다. 따라서 다른 방법을 찾아야 하는데, 이 문제는 DP (Dynamic Programming) 를 활용하여 해결할 수 있습니다.
DP 를 이용해 문제를 해결하기 위해, 먼저 i 번째 점을 첫 번째 집합에 포함시키는 경우와 두 번째 집합에 포함시키는 경우로 나누어 생각합니다.

DP 를 이용해 문제를 해결하기 위해, 먼저 i 번째 점을 첫 번째 집합에 포함시키는 경우와 두 번째 집합에 포함시키는 경우로 나누어 생각합니다.
그리고 DP[i][j] 를 i 번째 점까지 고려했을 때 첫 번째 집합에 j 개의 점이 포함되어 있는 경우와 두 번째 집합에 (N-j) 개의 점이 포함되어 있는 경우의 거리의 최소값으로 정의합니다.
이제 i 번째 점이 첫 번째 집합에 포함되는 경우와 두 번째 집합에 포함되는 경우를 모두 고려해보면서 DP 값을 구하면 됩니다.

즉, i 번째 점이 첫 번째 집합에 포함되는 경우를 예로 들면, 이전에 구한 DP 값들 중 i-1 번째 점이 첫 번째 집합에 있을 때의 DP 값을 참고하여 DP[i][j] 값을 구합니다. 이 때, i 번째 점과 첫 번째 집합에 있는 다른 점 간의 거리를 계산하면서 DP 값을 갱신합니다.
위와 같은 방법으로 DP 값을 구한 후, 마지막으로 DP[N][j] 값을 모두 확인하여 그 중 최소값을 찾으면 두 집합 간의 거리의 최소값을 구할 수 있습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, int>> v;
double answer = 1e9; // 초기값으로 충분히 큰 값 지정
// 두 점 사이의 거리 계산 함수
double get_distance(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return sqrt(dx * dx + dy * dy);
}
// 조합을 이용해 두 그룹으로 나누는 함수
void solve(int idx, int cnt, vector<int>& temp) {
    // 한 그룹의 크기가 n/2가 되었을 때
    if (cnt == n / 2) {
        double sum_x = 0, sum_y = 0;
        // 각 그룹의 합을 구함
        for (int i = 0; i < n; i++) {
            if (find(temp.begin(), temp.end(), i) != temp.end()) {
                sum_x += v[i].first;
                sum_y += v[i].second;
            } else {
                sum_x -= v[i].first;
                sum_y -= v[i].second;
            }
        }
        // 두 그룹간의 거리 계산하여 최소값 갱신
        answer = min(answer, get_distance(sum_x, sum_y, 0, 0));
        return;
    }
    // 그룹 크기가 n/2보다 작을 경우
    if (idx == n) {
        return;
    }
    // idx번째 건물을 포함할 경우
    temp.push_back(idx);
    solve(idx + 1, cnt + 1, temp);
    // idx번째 건물을 포함하지 않을 경우
    temp.pop_back();
    solve(idx + 1, cnt, temp);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        v.clear();
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            v.push_back(make_pair(x, y));
        }
        vector<int> temp; // 현재까지 선택한 건물들의 인덱스 저장
        answer = 1e9; // 초기화
        solve(0, 0, temp); // 조합 함수 호출
        cout.precision(12);
        cout << fixed << answer << '\n'; // 결과 출력
    }
    return 0;
}