BOJ 14889.스타트와 링크

입력

1 : N
2 ~ N+1 : 능력치

주의사항

1) 비트연산 헷갈리지 않기

구현방식

1) DFS 기반 완전탐색

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

int N, S[20][20];
int minimum = 1000000;

void dfs(int people,int team, int count) {
	int i, j;

	if (minimum == 0)
		return;

	if (count == N / 2) {
		vector<int> team_num[2];
		int team_skill[2] = { 0, };
		int ret;

		for (i = 0; i < N;i++) {
			if (team &(1 << i))
				team_num[1].push_back(i);
			else
				team_num[0].push_back(i);
		}
		for (i = 0; i < team_num[0].size()-1;i++) {
			for (j = i + 1;j < team_num[0].size();j++) {
				team_skill[0] += S[team_num[0][i]][team_num[0][j]];
				team_skill[0] += S[team_num[0][j]][team_num[0][i]];
				team_skill[1] += S[team_num[1][i]][team_num[1][j]];
				team_skill[1] += S[team_num[1][j]][team_num[1][i]];
			}
		}

		if (team_skill[0] > team_skill[1])
			ret = team_skill[0] - team_skill[1];
		else
			ret = team_skill[1] - team_skill[0];

		if (ret < minimum)
			minimum = ret;
	}
	else {
		for (i = people + 1; i < N; i++)
			dfs(i, team + pow(2, people), count + 1);
	}
}

int main(void) {
	int i, j;
	memset(S, 0, sizeof(S));
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		for (j = 0; j < N;j++) 
			scanf("%d", &S[i][j]);
	}
	
	for (i = 0; i < N;i++)
		dfs(i, 0, 0);

	printf("%d\n", minimum);
}