BOJ (C/C++) 14889번: 스타트와 링크

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

14889번: 스타트와 링크

---

풀이

백트래킹을 사용하여 팀원을 만들 수 있는 모든 경우의 수를 구함.

한 팀의 인원이 다 찼을 때, 다른 팀 인원을 구하고 각각 능력치 계산 후 차이의 최솟값을 구했다.

 

팀원이 2명이라 가정했을 때, 팀원 0,1이 같은 팀이 되는 경우는 팀원 1,0이 같은 팀이 되는 경우와 같기에 이 경우를 제외해야함.
(포함 시 시간초과)

팀원 1,2가 1팀, 팀원 3,4가 2팀인 경우도 동일한 경우이므로 이 경우도 제외해 줘야 함.

 

이 경우는 포함해도 통과는 되지만 제외했을 경우 시간이 2배 차이나는 것을 볼 수 있음

---

코드

#include <stdio.h>
#include <vector>
#include <limits.h>
using namespace std;

vector <int> T1;
int N, Min = INT_MAX;
int S[20][20];
bool visit[20];

void Cal() {
	int s = N / 2;
	vector <int> T2;
	int sum1, sum2, sum;
	sum1 = sum2 = 0;

	// team 2 members
	for (int i = 0; i < N; i++) {
		if (!visit[i]) T2.push_back(i);
	}

	//team 1
	for (int i = 0; i < s; i++) {
		for (int j = i + 1; j < s; j++) {
			int t1 = T1[i], t2 = T1[j];
			sum1 += S[t1][t2] + S[t2][t1];
		}
	}

	// team 2
	for (int i = 0; i < s; i++) {
		for (int j = i + 1; j < s; j++) {
			int t1 = T2[i], t2 = T2[j];
			sum2 += S[t1][t2] + S[t2][t1];
		}
	}

	sum = sum1 - sum2;
	if (sum < 0) sum = -sum;
	if (sum < Min) Min = sum;
}
void Get_diff(int n) {
	if (T1.size() == n) {
		Cal();
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!visit[i]) {

			// t1 = 0,1 / t1 = 2,3
			if (T1.size() && T1[T1.size() - 1] > i) continue;

			visit[i] = true;
			T1.push_back(i);
			Get_diff(n);
			visit[i] = false;
			T1.pop_back();

			// t1 = 0,1 t2 = 2,3 / t1 = 2,3 t2 = 0,1
			if (!T1.size()) return;
		}
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &S[i][j]);
		}
	}
	Get_diff(N / 2);
	printf("%d", Min);
	return 0;
}