백준 14889번 스타트와 링크 ( C++ )

문제

https://www.acmicpc.net/problem/14889

 

해설

비트마스킹을 이용하는 간단한 문제

if(__builtin_popcount == n/2)를 사용하면 훨씬 빠르게 켜진 비트의 수를 확인할 수 있음

코드

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
int mp[24][24], n, team1, team2,ret = 987654321;
vector<int> v,v2;
 
void go(int num){
  int cnt = 0;
  vector<int> v,v2;
  for(int i=0;i<n;i++){
    if(num&(1<<i)){
      cnt++;
      v.push_back(i);
    }
    else v2.push_back(i);
  }
  if(cnt != (n/2)) return;
 
  int tmp = 0;
  for(int i=0; i<n/2;i++){
    for(int j=i+1; j<n/2;j++){
      tmp = tmp + mp[v[i]][v[j]]+mp[v[j]][v[i]] - mp[v2[i]][v2[j]] - mp[v2[j]][v2[i]];
    }
  }
  ret = min(ret,abs(tmp));
}
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> mp[i][j];
    }
  }
 
  for(int i = n-1;i<(1<<n);i++){
    if(__builtin_popcount(i) != n / 2) continue; 
    go(i);
  }
 
  cout << ret;
}