[백준 14889] 스타트와 링크 (C#, C++) - soo:bak

문제 링크

14889번 - 스타트와 링크

설명

N명을 N/2명씩 두 팀으로 나눌 때, 두 팀의 능력치 차이의 최솟값을 구하는 문제입니다.

접근법

깊이 우선 탐색으로 N명 중 N/2명을 선택하는 모든 조합을 탐색합니다. 각 사람을 첫 번째 팀에 포함시키거나 포함시키지 않는 두 가지 선택지를 재귀적으로 탐색합니다.

첫 번째 팀에 N/2명이 선택되면 두 팀의 능력치를 계산합니다. 같은 팀에 속한 두 사람의 쌍에 대해 양방향 능력치를 모두 더하여 팀 점수를 구합니다.

모든 조합에 대해 두 팀 능력치의 차이를 계산하고 최솟값을 갱신합니다.

---

Code

C#

using System;

class Program {
  static int n;
  static int[,] s = new int[20, 20];
  static bool[] sel = new bool[20];
  static int ans = int.MaxValue;

  static void Dfs(int idx, int cnt) {
    if (cnt == n / 2) {
      var start = 0;
      var link = 0;
      for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
          var val = s[i, j] + s[j, i];
          if (sel[i] && sel[j]) start += val;
          else if (!sel[i] && !sel[j]) link += val;
        }
      }
      var diff = Math.Abs(start - link);
      if (diff < ans) ans = diff;
      return;
    }
    if (idx == n) return;

    sel[idx] = true;
    Dfs(idx + 1, cnt + 1);
    sel[idx] = false;
    Dfs(idx + 1, cnt);
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      for (var j = 0; j < n; j++) s[i, j] = int.Parse(parts[j]);
    }
    Dfs(0, 0);
    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n;
int s[20][20];
bool sel[20];
int ans = INT_MAX;

void dfs(int idx, int cnt) {
  if (cnt == n / 2) {
    int start = 0, link = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        int val = s[i][j] + s[j][i];
        if (sel[i] && sel[j]) start += val;
        else if (!sel[i] && !sel[j]) link += val;
      }
    }
    ans = min(ans, abs(start - link));
    return;
  }
  if (idx == n) return;

  sel[idx] = true;
  dfs(idx + 1, cnt + 1);
  sel[idx] = false;
  dfs(idx + 1, cnt);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> s[i][j];

  dfs(0, 0);
  cout << ans << "\n";

  return 0;
}