백준 : 14889

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

14889번: 스타트와 링크

#include<iostream>
#include<vector>
#include<algorithm>
#define INF 987654321;
using namespace std;

int N;

bool team[1001];

int S[1001][1001];

int Min = INF;

void DFS(int cur,int cnt) {

	if (cnt == N / 2) {
		vector <int> link;
		vector <int> star;

		for (int i = 1;i <= N;i++) {
			if (team[i]) link.push_back(i);
			else star.push_back(i);
		}
		int link_c = 0;
		int star_c = 0;

		for (int i = 0;i < N / 2;i++) {
			for (int j = 0;j < N / 2;j++) {
				if (i == j) continue;
				link_c += S[link[i]][link[j]];
				star_c += S[star[i]][star[j]];
			}
		}
		
		Min = min(Min, abs(link_c - star_c));

	}
	else {

		for (int i = cur + 1;i <= N;i++) {
			team[i] = true;
			DFS(i,cnt+1);
			team[i] = false;
		}

	}



}


int main() {
	cin >> N;
	for (int i = 1;i <= N;i++)
		for (int j = 1;j <= N;j++)
			cin >> S[i][j];

	DFS(0,0);
	cout << Min;
}