첫 번째 방법

필요한 지식

1. 조합

2. 재귀

접근

1. 재귀로 n/2개를 선택하고 그때의 값을 계산해 준다.

2. 조합의 가짓수를 줄이기 위해 첫 번째 깊이에서 i를 선택했다면 그 다음 깊이에선 i보다 큰수만 선택하게 해서 중복으로 체크하지 않게한다.

코드(C++)

#include <iostream>
#include <limits.h>
#include <algorithm>
using namespace std;
int arr[21][21], ans = INT_MAX, n;
int chk[21];
vector<int>v;
void cal() {
    int tmp = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (!chk[i] && (chk[i] ==  chk[j])) {
                tmp += arr[i][j];
                tmp += arr[j][i];
            }
            else if(chk[i] && (chk[i] == chk[j])) {
                tmp -= arr[i][j];
                tmp -= arr[j][i];
            }
        }
    }
    ans = min(ans, abs(tmp));
    return;
}
void go(int cnt, int pos) {
    if (cnt == 0) {
        cal();
        return;
    }
    for (int i = pos; i <= n; i++) {
        if (!chk[i]) {
            chk[i] = 1;
            go(cnt - 1, i + 1);
            chk[i] = 0;
        }
    }
    return;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> arr[i][j];
    go(n / 2, 1);
    cout << ans;
    return 0;
}

두 번째 방법

필요한 지식

1. 조합

2. next_permutation

접근

1. 첫 번째 방법과 다르지않다. next_permutation을 사용했다.

2. next_permutation을 수행하는 벡터에는 0과 1이 각각 n/2개씩 들어가게 초기화 시킨다.

next_permutation 을 수행하는 벡터안에 1~n의 숫자가 들어가게 되면 중복되게 확인하게 되어 시간초과가 발생한다.

코드(C++)

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;
int arr[21][21], ans = INT_MAX, n;
vector<int>v;
void cal() {
	int tmp = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (!v[i - 1] && (v[i - 1] == v[j - 1])) tmp += (arr[i][j] + arr[j][i]);
			else if (v[i - 1] && (v[i - 1] == v[j - 1])) tmp -= (arr[i][j] + arr[j][i]);
		}
	}
	ans = min(ans, abs(tmp));
	return;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (i <= n / 2)v.push_back(0);
		else v.push_back(1);
	}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> arr[i][j];
	do {
		cal();
	} while (next_permutation(v.begin(), v.end()));
	cout << ans;
	return 0;
}

결과

• 위(next_permutation), 아래(재귀)