🐣 문제

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

🐥 코드

#include <iostream>
#include <cmath>

using namespace std;
int arr[20][20];
int ans = 100000000;
bool visited[20];
int N;

void dfs(int cnt, int s){
	if(cnt == N/2){
		int a = 0;
		int b = 0;

		for(int i = 0; i < N; i++){
			for(int j = i+1; j < N; j++){
				if(visited[i] && visited[j]){
					a += arr[i][j];
					a += arr[j][i];
				}else if(!visited[i] && !visited[j]){
					b += arr[i][j];
					b += arr[j][i];
				}
			}
		}
		ans = min(ans, abs(a-b));
	}

	for(int i = 0; i < N; i++){
		if(visited[i] == false && i > s){
			visited[i] = true;
			dfs(cnt+1, i);
			visited[i] = false;
		}
	}
}

int main(){
	cin >> N;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++)
			cin >> arr[i][j];
	}

	dfs(0, -1);
	cout << ans << '\n';
	return 0;
}