글 읽기 - 50%에서 틀리네요..

lonecitizen 5년 전 0

dfs로 조합구하고 그걸로 sum구한담에 최소값 찾는건데..

반례를 알 수가 없네요..

도와주세요!

#include <iostream>
#include <vector>

using namespace std;
int N, map[21][21], combiCnt = 0, ans = 2e9;
vector<int> v;
vector<vector<int>> combi;

void dfs(int idx, int cnt, int flag) {
	if (idx > N) return;
	if (flag == 0) {
		dfs(idx + 1, cnt, 0);
		dfs(idx + 1, cnt, 1);
		return;
	}
	v.push_back(idx);


	if (cnt == N / 2) {
		vector<int> temp;
		combi.push_back(temp);
		for (int i = 0; i < v.size(); i++) combi[combiCnt].push_back(v[i]);
		combiCnt++;
	}

	dfs(idx + 1, cnt + 1, 0);
	dfs(idx + 1, cnt + 1, 1);

	v.pop_back();

}
int main()
{
	cin >> N;
	for (int n = 1; n <= N; n++) {
		for (int m = 1; m <= N; m++) {
			cin >> map[n][m];
		}
	}

	dfs(1, 1, 0);
	dfs(1, 1, 1);

	int cSize = combi.size();
	for (int i = 0; i < cSize / 2; i++) {
		int sumA = 0, sumB = 0;
		for (int j = 0; j < combi[i].size() - 1; j++) {
			int A = combi[i][j];
			int B = combi[i][j + 1];

			sumA += map[A][B];
			sumA += map[B][A];
		}

		sumA += map[combi[i][0]][combi[i].back()];
		sumA += map[combi[i].back()][combi[i][0]];

		for (int j = 0; j < combi[cSize - 1 - i].size() - 1; j++) {
			int A = combi[cSize - 1 - i][j];
			int B = combi[cSize - 1 - i][j + 1];

			sumB += map[A][B];
			sumB += map[B][A];
		}

		sumB += map[combi[cSize - 1 - i][0]][combi[cSize - 1 - i].back()];
		sumB += map[combi[cSize - 1 - i].back()][combi[cSize - 1 - i][0]];
		
		int subt = abs(sumA - sumB);

		if (subt < ans) ans = subt;
	}

	cout << ans;
}