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

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

 

 

문제 설명

n x n 배열이 주어졌을 때, 두 팀으로 나누어서 두 팀간의 능력치 차가 최소가 되는 경우를 출력하는 문제이다.

i번째와 j번째가 같은 팀이 되었을 때 능력치는 S(i,j) + S(j,i)이다.

 

주요 로직

1. 비트 마스킹이다.
-> 두 팀을 나누는 모든 경우의 수를 따져야 하므로 비트마스킹으로 경우마다 두 팀의 인원이 같은지 확인하고 능력치를 구하면 된다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,ret=987654321,arr[24][24];

int check(vector<int> v){
	int sum = 0;
	for(int i=0; i<v.size(); i++){
		for(int j=0; j<v.size(); j++){
			if(i == j) continue;
			sum += arr[v[i]][v[j]];
		}
	}
	return sum;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int i=0; i<(1<<n); i++){
		vector<int> v1;
		vector<int> v2;
		for(int j=0; j<n; j++){
			if(i & (1<<j)) v1.push_back(j);
			else v2.push_back(j);
		}
		if(v1.size() == v2.size()){
			int tmp1 = check(v1);
			int tmp2 = check(v2);
			ret = min(ret, abs(tmp1-tmp2));
		}
	}
	
	cout << ret << "\n";
	
	return 0;
}