[BOJ] 14889 스타트와 링크

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

 

문제 풀이 1: - 재귀 

ateam[20], bteam[20] 

1~N 번 중 위 두 팀에 속할 선수들을 재귀로 선택

두 팀 모두 인원수가 n/2일 때, 능력치 계산

 

시간: 20ms

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <cmath>
#include <string>
#define INF 987654321
using namespace std;


int n,arr[21][21],ateam[21],bteam[21],res;

void func(int at,int bt,int cur) {
	if (at== n / 2 && bt==n/2) {
		int asum = 0, bsum = 0;
		for (int i = 1; i < n / 2; i++) {
			for (int j = 0; j < i; j++) {
				asum += arr[ateam[i]][ateam[j]] + arr[ateam[j]][ateam[i]];
				bsum += arr[bteam[i]][bteam[j]] + arr[bteam[j]][bteam[i]];
			}
		}
		res = min(res, abs(asum - bsum));
		return;
	}
	if (at < n / 2) {
		ateam[at] = cur;
		func(at + 1, bt, cur + 1);
	}
	if (bt < n / 2) {
		bteam[bt] = cur;
		func(at, bt + 1, cur + 1);
	}
}
int main()
{
	ios::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];
		}
	}
	res = INF;
	func(0,0,0);
	
	cout << res << '\n';
	return 0;
}

 

 

문제 풀이 2: - 비트 마스킹

2팀으로 나누는 모든 경우의 수를 구한다 -> $2^N$개

이 중 2팀이 동일한 인원수로 나눠지는 경우에만 연산을 한다. ->calculator() 함수 호출

calculator() 함수에서는 비트가 1인 팀, 0인 팀끼리 각각 능력치의 합을 구해, 이 두 팀의 능력치 차의 최솟값을 결과 변수에 갱신해준다.

 

시간: 172ms

 

소스 코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <cmath>
#include <string>
#define INF 987654321
using namespace std;

int n,arr[21][21],res;

void calculator(int visit) {
	int a=0,b=0;
	for (int i = 0; i <n; i++) {
		if (visit&(1 << i)) {
			for (int j = 0; j < i; j++) {
				if (visit&(1 << j)) a += arr[i][j] + arr[j][i];
			}
		}
		else {
			for (int j = 0; j < i; j++) {
				if (!(visit&(1 << j))) b += arr[i][j] + arr[j][i];
			}
		}
		
	}
	res = min(res, abs(a-b));
}
int main()
{
	ios::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];
		}
	}
	res = INF;
	for (int i = 0; i < pow(2, n); i++) {
		// 비트 i에서 1의 개수 찾기
		int cnt,tmp = i;
		for (cnt = 0; tmp; cnt++) {
			tmp &= tmp - 1; 
		}
		if (cnt != n / 2) continue;
		calculator(i);
	}
	cout << res << '\n';
	return 0;
}