[SWEA] 4012. 요리사

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 짝수 N개의 식재료가 있습니다.  각각 N/2, N/2의 식재료들을 이용해 요리 A,B를 만들려고 합니다. 식재료는 둘중 하나의 요리를 위해 들어갑니다. 그리고 N * N의 배열로 각 재료들 간의 궁합 점수가 주어집니다. 각 요리에 쓰인 식재료들의 궁합 점수의 합이 요리 점수가 됩니다. A , B요리간의 점수 차의 최소를 구하는 것이 문제입니다.

 

 이것도 앞서 문제와 같이 next_permutation으로 풀었습니다. 단순이 n C n/2를 구하는 것이라서 어렵지 않게 풀었습니다. 주의해야할 점은 Si,j와 Sj,i가 다르다는 것입니다.

 

 

	#include<iostream>
	#include<vector>
	#include<algorithm>
	using namespace std;
	int tc,n,ans;
	int comb[16][16];
	vector<bool> vt;
	int main(void)
	{
	cin >> tc;
	for (int t = 1; t <= tc; t++)
	{
	cin >> n;
	ans = 987654321;
	vt.clear();
	for (int i = 0; i < n / 2; i++)
	vt.push_back(0);
	for (int i = 0; i < n / 2; i++)
	vt.push_back(1);
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
	{
	cin >> comb[i][j];
	}
	}
	do
	{
	vector<int> A;
	vector<int> B;
	int a = 0, b = 0;
	for (int i = 0; i < vt.size(); i++)
	{
	if (vt[i])
	A.push_back(i);
	else
	B.push_back(i);
	}
	for (int i = 0; i < A.size(); i++)
	{
	for (int j = 0; j < A.size(); j++)
	{
	if (i != j)
	{
	a += comb[A[i]][A[j]];
	b += comb[B[i]][B[j]];
	}
	}
	}
	int num = abs(a - b);
	ans = ans > num ? num : ans;
	} while (next_permutation(vt.begin(), vt.end()));
	cout <<'#'<<t<<' '<< ans << '\n';
	}
	}

view raw [SWEA] 4012.cpp hosted with ❤ by GitHub