[BOJ][실3][14889] 스타트와 링크

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

n명을 두 팀으로 나누어야 합니다. A팀 n/2명을 고르는 백트래킹을 진행합니다. B팀에는 우선 모든 인원을 넣어두고, A팀의

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int arr[25][25];
int team[25];
vector<int> teamB;
int ans = 987654321;
void recur(int depth, int start) {
  if (depth == n / 2) {
    vector<int> copy(teamB);
    for (int i = 0; i < depth; i++) {
      auto it = find(copy.begin(), copy.end(), team[i]);
      copy.erase(it);
    }
    /*cout << "teamA teamB\n";
    for (int i = 0; i < depth; i++) {
      cout << team[i] << " " << copy[i] << "\n";
    }*/
    int a = 0, b = 0;
    for (int i = 0; i < n / 2; i++) {
      for (int j = i+1; j < n / 2; j++) {
        a += arr[team[i]][team[j]];
        a += arr[team[j]][team[i]];
        b += arr[copy[i]][copy[j]];
        b += arr[copy[j]][copy[i]];
      }
    }
    ans = min(ans, abs(a - b));
    return;
  }

  for (int i = start; i < n; i++) {
    team[depth] = i;
    recur(depth + 1, i + 1);
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;

  for (int i = 0; i < n; i++) {
    teamB.push_back(i);
    for (int j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }
  recur(0, 0);
  cout << ans;

  return 0;
}

Success Notice: 수고하셨습니다.