백준 14889

비효율적이지만 샘플은 잘 돌아가는 코드.

채점 결과는 당연히 시간초과. 큰 수에 대해서 계산이 시간 안에 끝날 수가 없다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ABIL_MAX 20000; // since a team has at most 10 people 
						// and each pair increases 100 ability points.
						// For safety, define max to bo 10*10*100*2
int main(){
	int n;
	cin >> n;
	
	vector<vector<int> > abil(n,vector<int>(n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> abil[i][j];
		}
	}
	
	vector<int> memb;
	for(int i = 0;i < n; i++){
		memb.push_back(i);
	}
	
	int diff=ABIL_MAX;
	
	do{
		int abil1=0, abil2=0;
		int cur_diff=0;
		for(int i = 0; i < n/2; i++){
			for(int j = 0; j < n/2; j++){
				abil1 += abil[memb[i]][memb[j]];
				abil2 += abil[memb[n/2+i]][memb[n/2+j]];
			}
		}
		cur_diff = abil1<abil2 ? abil2-abil1 : abil1-abil2;
		diff = diff<cur_diff ? diff : cur_diff;
	} while( next_permutation( memb.begin() , memb.end() ) );
	
	cout << diff;
	return 0;
}