백준 14889 스타트와 링크

문제:

14889번: 스타트와 링크

코드:

전체 경우의 수(tb의 상한 + 1, as의 크기)는 1 << (N/2)가 아니라 1 << N이다.

#include <iostream>
#include <algorithm>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int N, ts, tb;
int S[20][20];
int as[1 << 20];
int ply[10];
int ans = 9000;
void bf(int i, int s, int b, int a) {
	if (s == ts) {
		if (as[tb ^ b]) {
			int d = abs(a - as[tb ^ b]);
			if (d < ans) ans = d;
		}
		else as[b] = a;
		return;
	}
	for (; i < N; ++i) {
		int na = a;
		f(p, s) na += S[ply[p]][i];
		ply[s] = i;
		bf(i + 1, s + 1, b | (1 << i), na);
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	ts = N / 2; tb = (1 << N) - 1;
	f(r, N) f(c, N) cin >> S[r][c];
	f(r, N) for (int c = r + 1; c < N; ++c) S[r][c] += S[c][r];
	bf(0, 0, 0, 0);
	cout << ans;
	return 0;
}