4012. [모의 SW 역량테스트] 요리사

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

간단히 그룹 분리해서 2개씩 대칭 합 해주고 차이의 최소값 구하면 됨.

 

 

 

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int N;
int arr[17][17];
bool visit[17];
int result;
vector<int> group1;
vector<int> group2;

int cal()
{
	int cost1 = 0;
	int cost2 = 0;
	int cost = 0;

	for (int i = 0; i < group1.size(); i++)
	{
		for (int j = i + 1; j < group1.size(); j++)
		{
			cost1 += arr[group1[i]][group1[j]];
			cost1 += arr[group1[j]][group1[i]];
		}
	}

	for (int i = 0; i < group2.size(); i++)
	{
		for (int j = i + 1; j < group2.size(); j++)
		{
			cost2 += arr[group2[i]][group2[j]];
			cost2 += arr[group2[j]][group2[i]];
		}
	}
	cost = abs(cost1 - cost2);

	return cost;

}

void DFS(int cur, int num)
{
	if (num == N/2)
	{
		for (int i = 1; i <= N; i++)
		{
			if (visit[i])
			{
				group1.push_back(i);
			}
			else
			{
				group2.push_back(i);
			}
		}

		int cost = cal();
		if (result > cost)
		{
			result = cost;
		}
		group1.clear();
		group2.clear();
		return;
	}


	for (int i = cur + 1; i <= N; i++)
	{
		visit[i] = true;
		DFS(i, num + 1);
		visit[i] = false;
	}

}

int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N;
		result = 987654321;


		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				cin >> arr[i][j];
			}
		}


		for (int i = 1; i <= N; i++)
		{
			visit[i] = true;
			DFS(i,1);
			visit[i] = false;
		}

		cout << "#" << test_case << " " << result << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}