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

 

1. 비트연산을 통해서 두개의 팀으로 나올 수 있는 모든 경우의 수를 구함. 

 

ex)

abcdefgh

11001010 

{a,b,e,g}, {c,d,f,h} 두팀으로 나뉘어짐. 

 

abcdefgh

11001011 

{a,b,e,g,h}, {c,d,f} 다른 한팀이 인원이 더 많으므로 continue;  

 

2. 이차원 배열에서 해당하는 팀원의 인덱스값을 통해 팀의 sum 값을 갱신해나간다.

3. 두 팀의 차이값이 이전에 구했던 차이값보다 작으면 계속해서 갱신

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std; 
int min_number = INT_MAX; 
int main() {
	int n; cin >> n; 
	vector <vector<int>>v(n, vector<int>(n, 0)); 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j]; 
		}
	}
	for (int i = 0; i < (1 << n); i++) {
		int cnt = 0; 
		for (int j = 0; j < n; j++) if ((i & (1 << j)))cnt++; 		
		if (cnt != n / 2)continue; 
		vector<int> a_team; 
		vector<int> b_team; 
		for (int j = 0; j < n; j++) {
			if (i & (1 << j))a_team.push_back(j);
			else b_team.push_back(j); 
		}
		int sum_a = 0; 
		int sum_b = 0; 
		for (int j = 0; j < n / 2; j++) {
			for (int k = 0; k < n / 2; k++) {
				if (j == k)continue; 
				sum_a += v[a_team[j]][a_team[k]]; 
				sum_b += v[b_team[j]][b_team[k]];
			}
		}
		min_number = min(abs(sum_a - sum_b), min_number); 
	}
	cout << min_number; 
}

14889번: 스타트와 링크