백준_15661_링크와 스타트

① 비트마스크 풀이

백준 14889 [스타트와 링크] 문제와 거의 똑같지만 조건이 살짝 다른 문제였다. 스타트팀과 링크팀의 인원수가 같지 않아도 되고 1명 이상이기만 하면 되는 문제였다. 따라서, 비트마스크로 팀을 나눌때 반복문의 i를 00001111이 아니라 0부터 시작해야 한다. 또한, 팀의 능력치를 구할 때도 스타트팀과 링크팀의 인원수를 고려해서 따로 구해야 했다. (능력치를 계산하는 조건도 각 팀이 1명 이상이기만 하면 구해야 한다.)

#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 = 0; i < (1 << N); i++) {
		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() > 0 && team2.size() > 0) { // i를 계속 1씩 증가시키다가, 각 팀에 1명 이상 있는 경우
			team1_sum = 0;
			team2_sum = 0;
			for (int i = 0; i < team1.size(); i++) { // 팀 내에서 2명씩 선택하는 모든 조합에 대해 능력치 더하기.
				for (int j = i + 1; j < team1.size(); j++) {
					team1_sum += S[team1[i]][team1[j]] + S[team1[j]][team1[i]];
				}
			}
			for (int i = 0; i < team2.size(); i++) { // 팀 내에서 2명씩 선택하는 모든 조합에 대해 능력치 더하기.
				for (int j = i + 1; j < team2.size(); j++) {
					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;
}

② 재귀 풀이

#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() > 0 && team2.size() > 0) { // i를 계속 1씩 증가시키다가, 각 팀에 1명 이상 있는 경우
			team1_sum = 0;
			team2_sum = 0;
			for (int i = 0; i < team1.size(); i++) { // 팀 내에서 2명씩 선택하는 모든 조합에 대해 능력치 더하기.
				for (int j = i + 1; j < team1.size(); j++) {
					team1_sum += S[team1[i]][team1[j]] + S[team1[j]][team1[i]];
				}
			}
			for (int i = 0; i < team2.size(); i++) { // 팀 내에서 2명씩 선택하는 모든 조합에 대해 능력치 더하기.
				for (int j = i + 1; j < team2.size(); j++) {
					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;
}