설계 단계

축구 N명(짝수)
팀을 두 팀으로 나눔(A팀과 B팀)

능력치 S_ij->같은 팀에 i, j가 속했을때 더해지는 능력치
팀의 능력치는 S_ij의 총합
S_ji는 S_ij와 다를 수 있음

스타트팀과 링크 팀의 능력치 차이를 최소로 하려고 함

팀원이 N명이면 N / 2명은 A팀에 N / 2명은 B팀에
넥스트퍼뮤테이션을 이용하면
1인팀 0인팀 나눠서 넣을 수 있음



vector<int> v;

for (int i = 0; i < N / 2; i++) {
	v.push_back(1);
}
for (int i = 0; i < N / 2; i++) {
	v.push_back(0);
}

sort(v.begin(), v.end());

int min_result = 98765432;

do {

	vector<int> A;
	int A_SUM = 0;
	vector<int> B;
	int B_SUM = 0;

	for (int i = 0; i < arr.size(); i++) {
		if (v[1]) { A.push_back(arr[i]); }
		else { B.push_back(arr[i]); }
	}

	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= A.size(); j++) {
			if (i == j) { continue; }
			A_SUM += MAP[A[i]][A[j]];
		}
	}

	for (int i = 1; i <= B.size(); i++) {
		for (int j = 1; j <= B.size(); j++) {
			if (i == j) { continue; }
			B_SUM += MAP[B[i]][B[j]];
		}
	}

	A.clear();
	B.clear();

	min_sum >= abs(A_SUM - B_SUM) ? min_sum = abs(A_SUM - B_SUM) ? ;

} while (next_permutation(v.begin(), v.end()));

풀이의 핵심

• 조합
  • 넥스트 퍼뮤테이션으로 조합을 뽑아낼 수 있음

삽질 포인트

• V[i] 대신 V[1]로 쓴 것... 이런 실수 하면 시험장에서 멘붕옴 ㅜㅜ

정답 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int MAP[20 + 1][20 + 1];


vector<int> v;

int min_result = 98765432;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &MAP[i][j]);
		}
	}

	vector<int> arr;
	for (int i = 1; i <= N; i++){
		arr.push_back(i);
	}

	for (int i = 0; i < N / 2; i++) {
		v.push_back(1);
	}
	for (int i = 0; i < N / 2; i++) {
		v.push_back(0);
	}

	sort(v.begin(), v.end());

	do {

		vector<int> A;
		int A_SUM = 0;
		vector<int> B;
		int B_SUM = 0;

		for (int i = 0; i < arr.size(); i++) {
			if (v[i] == 1) { A.push_back(arr[i]); }
			else { B.push_back(arr[i]); }
		}

		for (int i = 0; i < A.size(); i++) {
			for (int j = 0; j < A.size(); j++) {
				if (i == j) { continue; }
				A_SUM += MAP[A[i]][A[j]];
			}
		}

		for (int i = 0; i < B.size(); i++) {
			for (int j = 0; j < B.size(); j++) {
				if (i == j) { continue; }
				B_SUM += MAP[B[i]][B[j]];
			}
		}

		A.clear();
		B.clear();
	//	printf("A : %d B : %d\n", A_SUM, B_SUM);

		min_result = (min_result >= abs(A_SUM - B_SUM)) ? abs(A_SUM - B_SUM) : min_result;

	} while (next_permutation(v.begin(), v.end()));

	
	printf("%d", min_result);


}