[BOJ] 14889번 스타트와 링크

문제 바로가기

접근

시작할 때 모든 인원을 team1으로 배정해두고, 조합을 구하는 과정에서 team2로 이동시켰다. N+1 길이의 일차원 배열을 만들어 0과 1을 각각 팀에 속한, 속하지 않은 상태로 표시했다. 그리고 조합이 만들어지면 그때 team1과 team2의 능력치를 더해서 두 팀의 능력치 차이가 가장 작을 때를 구했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 987654321

int N;
int arr[21][21] = {0};
int team1[21] = {0}, team2[21] = {0};
bool visited[21] = {false};
int sum1 = 0, sum2 = 0;
int minval = INF;

void combination(int s) {
  team1[s] = 0; // move 's' to team2
  team2[s] = 1;

  if(count(team1 + 1, team1 + N + 1, 1) == N / 2) {
    sum1 = sum2 = 0;

    for(int i = 1; i <= N; i++) {
      if(!team1[i]) continue;
      for(int j = 1; j < i; j++) {
        if(!team1[j]) continue;
        sum1 = sum1 + arr[i][j] + arr[j][i];
      }
    }

    for(int i = 1; i <= N; i++) {
      if(!team2[i]) continue;
      for(int j = 1; j < i; j++) {
        if(!team2[j]) continue;
        sum2 = sum2 + arr[i][j] + arr[j][i];
      }
    }

    minval = min(minval, abs(sum1 - sum2));
    return;
  }

  for(int i = s; i <= N; i++) {
    if(!visited[i]) {
      visited[i] = true;
      combination(i);
      team1[i] = 1;
      team2[i] = 0;
      visited[i] = false;
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);

  cin >> N;
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= N; j++)
      cin >> arr[i][j];
    team1[i] = 1;
  }

  combination(1);
  cout << minval;
}