백준_14889_스타트와 링크

① 비트마스크 풀이

비트마스크를 이용해서 풀었다. N개의 비트로 각 사람이 어느팀에 속하는지를 표현하면 되는 문제였다.

for문의 i를 이용해서 사람들을 두 팀으로 나누는 모든 경우를 따졌고, 두 팀의 사람수가 같게 되면 능력치 계산을 했다.

자세한 코드 설명은 주석으로 작성했다.

#include <iostream>
#include <vector>
#include <algorithm> // min()
#include <cmath> // abs()
#include <climits> // INT_MAX
#define MAX 20

using namespace std;

int N, S[MAX][MAX], x, team1_sum, team2_sum, result = INT_MAX;
vector<int> team1, team2;

// 어떻게 팀을 반띵하는 모든 경우를 다 탐색할까?? N개의 비트로 각 사람이 어느팀에 속하는지 표현!
void solve() {
	for (int i = (1 << (N / 2 + 1)) - 1; i < (1 << N); i++) { // n=8일때, 10000 - 1 은 1111 이니까 이를 이용해서 i=00001111 부터 시작
		team1.clear(); // 사람들을 두 팀으로 나누는 경우들을 계산할때마다 처음에 팀을 초기화 해야함.
		team2.clear();
		for (int j = 0; j < N; j++) { // N개의 비트에 대해
			if ((i & (1 << j)) == 0) team1.push_back(j); // 해당 비트가 0이면 team1에 넣고,
			else team2.push_back(j); // 해당 비트가 1이면 team2에 넣음.
		}

		if (team1.size() == N / 2 && team2.size() == N / 2) { // i를 계속 1씩 증가시키다가, 팀이 반띵되는 순간이 오는 경우
			team1_sum = 0;
			team2_sum = 0;
			for (int i = 0; i < N / 2; i++) { // 팀 내에서 2명씩 선택하는 모든 조합에 대해 능력치 더하기.
				for (int j = i + 1; j < N / 2; j++) {
					team1_sum += S[team1[i]][team1[j]] + S[team1[j]][team1[i]];
					team2_sum += S[team2[i]][team2[j]] + S[team2[j]][team2[i]];
				}
			}
			result = min(result, abs(team1_sum - team2_sum)); // 두 팀의 능력치 차이의 최솟값 갱신
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> x;
			S[i][j] = x;
		}
	}
	solve();
	cout << result << '\n';
	return 0;
}

② 재귀 풀이

재귀를 이용했다. 현재 사람을 team1에 넣는 경우와 team2에 넣는 경우 2가지로 나누어서 각각 재귀함수를 호출했다.

처음에 함수 종료 조건을 두 팀의 인원수가 같아지는 순간으로  설정하는 실수를 해서 답이 제대로 나오지 않았다. 함수 종료 조건은 N명의 사람들을 모두 팀에 넣었을 때(각 팀의 인원수와 상관 없이)임을 주의해야 한다.

#include <iostream>
#include <vector>
#include <algorithm> // min()
#include <cmath> // abs()
#include <climits> // INT_MAX
#define MAX 20

using namespace std;

int N, x, S[MAX][MAX], result = INT_MAX, team1_sum, team2_sum;
vector<int> team1, team2;

void solve(int player_num) {
	if (player_num == N) {
		if (team1.size() == N / 2 && team2.size() == N / 2) {
			team1_sum = 0;
			team2_sum = 0;
			for (int i = 0; i < N / 2; i++) {
				for (int j = i + 1; j < N / 2; j++) {
					team1_sum += S[team1[i]][team1[j]] + S[team1[j]][team1[i]];
					team2_sum += S[team2[i]][team2[j]] + S[team2[j]][team2[i]];
				}
			}
			result = min(result, abs(team1_sum - team2_sum));
		}
		return;
	}
	//재귀 부분
	team1.push_back(player_num);
	solve(player_num + 1);
	team1.pop_back();

	team2.push_back(player_num);
	solve(player_num + 1);
	team2.pop_back();
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> x;
			S[i][j] = x;
		}
	}
	solve(0);
	cout << result << '\n';
	return 0;
}