[UVa #10911] Forming Quiz Teams

문제 설명

문제 링크
$n$명의 사람 쌍(즉 사람은 $2n$명)의 2차원 위치 좌표가 주어진다.
$n$쌍을 만들려고 한다. 각 쌍의 사람들의 거리의 합이 최소는?

알고리즘

책에서 DP를 이용해서 풀 수 있다고 되어 있어서 그냥 넘어가려다 백트래킹+가지치기로도 풀 수 있다고 해서 푼 문제
최대 8쌍이므로 모든 경우를 백트래킹으로 서치해서 계산하되 중간 중간에 계산된 최적의 값보다 커지는 경우는 더 계산할 필요가 없으므로 가지치기 해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 1000000000

int n;
double ans = INF;
double pos[17][2];
bool selected[17];


double Dir(int pos1, int pos2) {
    return sqrt(pow((pos[pos1][0] - pos[pos2][0]), 2) + pow((pos[pos1][1] - pos[pos2][1]), 2));
}

void Solve(double sum = 0) {
    int cnt = 0;
    for (int i = 1; i <= 2 * n; ++i)
        if (selected[i]) cnt++;

    if (cnt == 2 * n) {
        ans = min(ans, sum);
        return;
    }
    
    // 가지치기
     if (ans < sum) return;

    int first;
    for (int i = 1; i <= 2 * n; ++i) {
        if (!selected[i]) {
            first = i;
            break;
        }
    }
    selected[first] = true;


    for (int second = 1; second <= 2 * n; ++second) {
        if (second == first) continue;
        if (selected[second]) continue;

        selected[second] = true;
        Solve(sum +Dir(first, second));
        selected[second] = false;
    }

    selected[first] = false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for (int tc = 1; true; ++tc) {
        cin >> n;
        if (n == 0) break;

        ans = INF;
        for (int i = 1; i <= 2 * n; ++i) {
            string name;
            cin >> name >> pos[i][0] >> pos[i][1];
        }

        Solve();

        cout << fixed;
        cout.precision(2);
        cout << "Case " << tc << ": " << round(ans * 100) / 100.0 << '\n';

    }
}

느낀 점...

파란 책이라고 부르던가... 알고리즘 트레이닝 책을 보고 푼 첫 문제
사용법을 잘 모르는 건지 모르겠지만 UVa 사이트가 되게 불친절하다.
문제 찾기도 까다롭고 제출해도 결과 페이지로 이동해야 결과가 보이고 광고도 많고...
심지어 이 문제에서 소수 둘째 자리에서 반올림하라 해서 118.40을 118.4로 출력했더니 틀렸다고 한다. 그래도 책 따라서 풀어볼 예정