백준 15661

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

 

이 문제의 경우 다르게보면 조합이지만 이 문제의 분류가 비스마스킹으로 되어 있어서 비스마스킹으로 풀려구 생각했다
이 문제의 비트마스킹은 총 나는 2개를 사용 했는데 일단 team의 점수를 저장하는데 사용 했다 (이 부분에서 좀더  최적화가 가능하나 귀찮아서 진행 하지않았다) 두번째로는 팀들을  나누는데 비트마스킹을 사용했다.

 

 

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}

 

나는 일단 teamP라는 곳에 두명이 차지했을 때의 점수를 넣어줬다 위에처럼 1001일때는 5임으로 4번과 1번팀이 같이 되어있을 때를 나타내며 각팀이 만들어내는 숫자에 따라 점수를 넣어줬다

 

 

 

 

숫자 일단 이문제의 경우 이렇게 1번팀 0번팀으로 나눌수 있는데 숫자 5의 경우 팀을 위에 그림처럼 나누게 된다

for (int i = 1; i < (1<<n); i++) {
	for (int j = 0; j <= n; j++) {
		if (i & (1 << j))
			team1.push_back(j);
		else
			team2.push_back(j);
	}

이 부분의로직은 이렇게 되는데 i=1부터 시작한다 그  이유는 0번비트만 있을 때는 팀을 만들 수 없으므로 0번 비트  1번 비트 2개가 있는 상황 부터 시작하기 위해서 1번 부터 비트를 사용한다 또한 1<<n 을한 이유는 우리의 테스트 케이스 4를 예시로 들면 비트 4개로 만들수 있는 최댓값은 15인데 1<<4는 16이므로 이부분보다 작을 동안만 우리는 연산을 해주면된다

j변수를 사용하는 루프의 경우는 이제 각비트가 어떤 비트인지 판별하기 위해서 해당 연산을 진행하고 0인지 1인지에 따라 팀에 분배해주게 된다

 

그후 우리는 두명만이 각 짝을 이뤄 점수가 있으므로

		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}

이런 식으로 각 팀의 연산을 해준다

 

전체 코드는 아래와 같다

#include <iostream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
int arr[20][20];
vector<int> team1;
vector<int> team2;
int maxresult = 1e9;
int teamP[2097152];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			int teamNum = (1 << i) | (1 << j);
			teamP[teamNum] = arr[i][j]+arr[j][i];
		}
	}
	int sum1 = 0;
	int sum2 = 0;
	
	for (int i = 1; i < (1<<n); i++) {
		for (int j = 0; j <= n; j++) {
			if (i & (1 << j))
				team1.push_back(j);
			else
				team2.push_back(j);
		}
		for (int k = 0; k < team1.size(); k++) {
			for (int p = k + 1; p < team1.size(); p++) {
				sum1 += teamP[(1 << team1[k]) | (1 << team1[p])];
			}
		}
		for (int k = 0; k < team2.size(); k++) {
			for (int p = k + 1; p < team2.size(); p++) {
				sum2 += teamP[(1 << team2[k]) | (1 << team2[p])];
			}
		}
		if (team1.size() && team2.size())
			maxresult = min(maxresult, abs(sum1 - sum2));
		team1.clear();
		team2.clear();
		sum1 = 0;
		sum2=0;
	}

	cout << maxresult;
}