백준 14889 스타트와 링크 C풀이 - DFS

 

 

 

백준 회사에서 축구대회를 한다.

팀원을 짜고 싶은데 시너지가 잘맞는 팀원이 있고 아닌 팀원들이 있어서 잘 짜야한다.

물론 재미있게 플레이하기 위해 전체적인 실력이 비슷해야한다. (20명인거보니 골키퍼는 고려안하나봐)

 

문제의 조건은 다음과 같다.

1. 두 팀의 능력치가 가장 비슷한 경우를 찾기

2. 두 팀의 인원은 같다.(N은 짝수)

3. 한 명이 특정 팀에 들어갈 경우 그 팀에 있는 모든 사람들과의 시너지를 계산해야한다.

 

 

 

전체코드

#include <stdio.h>
#include <random>
int N;
int Min = 987654321;
int Map[21][21];
int used[21];
int abs(int x) {
	if (x < 0) return -x;
	return x;
}
//시너지 계산
int check() {
	int team1=0, team2 = 0;
	for (int i = 0; i < N; i++) {
		if (used[i]) {
			for (int j = i + 1; j < N; j++) {
				if (used[j]) {
					team1 += Map[i][j] + Map[j][i];
				}
			}
		}
		else {
			for (int j = i + 1; j < N; j++) {
				if (!used[j]) {
					team2 += Map[i][j] + Map[j][i];
				}
			}
		}
	}
	return abs(team1 - team2);
}
//팀선택
void dfs(int num, int idx) {
	if (num == N/2 ) {
		int tmp = check();
		if (tmp < Min) Min = tmp;
		return;
	}

	for (int i = idx+1; i < N; i++) {
		if (used[i]) continue;
		used[i] = 1;
		dfs(num + 1, i);
		used[i] = 0;
	}
	return; 
}

int solve() {
	for (int i = 0; i < N; i++) {
		used[i] = 1;
		dfs(1, i);
		used[i] = 0;
	}
	return 0;
}
int main() {
	scanf("%d", &N);
	//N = 20;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &Map[i][j]);
			//Map[i][j] = rand() % 101;
		}
	}
	solve();
	printf("%d\n", Min);
	return 0;
}