공부흔적

문제 링크

풀이 ) 완전 탐색

  먼저 n명에 대해서 두 팀으로 나누어서 스타트팀은 0으로 링크팀은 1로 team 배열에 저장했다.

  예를 들어 6팀인 경우 team 배열은 {0, 0, 0, 1, 1, 1}로 시작한다.

  이후 team배열을 순회하면서 두 개의 커서에 대해서 두 커서가 가리키는 사람이 같은 팀이면 즉 team[i] == team[j]이면 어느 팀인지 확인하여 (team[i] == 0) 그 팀의 점수에 추가해준다. (start(link) += stat[i][j] + stat[j][i])

  한 배열을 다 순회한 후 각 팀은 점수차를 현재의 답과 비교하여 최솟값을 구해준다.

  다음에는 {0, 0, 0, 1, 1, 1}의 다음 조합인 {0, 0, 1, 0, 1, 1}을 확인한다.

  * 다음 조합을 구하는 것은 다음 순열을 구하는 next_permutation( )을 사용하여 구했다.

  같은 방식으로 값을 구한 후 비교한다.

  next_permutation( )이 -1을 리턴하는 {1, 1, 1, 0, 0, 0}의 다음에 while문을 빠져나오면서 종료된다.

  아래의 코드에서는 {0, 0, 0, 1, 1, 1}의 경우를 건너뛰었지만 {1, 1, 1, 0, 0, 0}의 경우에 다시 확인해주기 때문에 빠뜨리지 않았다.

#include <cstdio>
#include <cstdlib>	// abs()
#include <algorithm>	// min()
using namespace std;

int main(void)
{
  int n, stat[21][21] = {0, }, team[21] = {0, }, ans = 1e9;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      scanf("%d", stat[i]+j);

  for(int i = 0; i < n/2; ++i)
    team[n-i-1] = 1;
  // {0, 0, ..., 0, 1, 1, ..., 1}

  while(next_permutation(team, team+n)){
    int start = 0, link = 0;
    for(int i = 1; i < n; ++i){
      for(int j = 0; j < i; ++j){
        if(team[i] == team[j]){
          if(team[i] == 0)
            start += stat[i][j]+stat[j][i];
          else
            link += stat[i][j]+stat[j][i];
        }
      }
    }
    ans = min(ans, abs(start-link));
  }
  printf("%d\n", ans);
  return 0;
}

주의점 )

  중복된 경우를 세고 있다.  ex ) {0, 1, 0, 1, 1, 0} - {1, 0, 1, 0, 0, 1}

  이 문제점에 대해서는 반복문을 실행하는 횟수를 _nC_n/2/2로 제한하면 해결할 수 있다. 혹은 다음 순열과 현재 순열을 비트로 비교했을 때 같은 인덱스의 원소에 대해서 서로 일치하는 것이 하나도 없는 경우 종료해줘도 된다고 생각된다.

  ex ) {0, 1, 1, 1, 0, 0} -> {1, 0, 0, 0, 1, 1} 종료