[백준] 14889 스타트와 링크 C++

문제 : https://www.acmicpc.net/problem/14889

 

해설

N / 2 명을 순서에 상관없이 뽑아 시너지를 더해야한다. 여기에서 조합이 사용된다.

조합을 통해서 N/2를 순서에 상관없이 뽑았다면, 시너지의 총합을 구하고 스타트팀과 링크팀의 시너치 총합의 최소값을 구해야한다.  (2차원 배열을 전부 순회해서 시너지의 합을 구한다)

Combi라는 함수를 통해 조합의 경우의 수를 구하고 check배열을 통해 각팀의 시너지 총합을 구했다.

 

후기

조합을 백트레킹으로 구현을 하는데는 시간이 얼마 걸리지 않았지만 시너지의 총합을 어떻게 구할지 고민하는데 시간을 많이 썻던 문제이다.

아이디어는 단순한데, 이 아이디어를 생각하는게 쉽지 않았다.

중간에 정확한 시너지의 합을 구하기 위해서 check배열을 통해 스타트팀과 링크팀의 시너지의 합을 정확하게 구하는 부분도 중요 한듯 했다.

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;

vector<vector<int>> input(21, vector<int>(21, 0));
bool check[21];
int n;
int ret = 999999999;

void Combi(int cnt, int prev)
{
	if (cnt == n / 2)
	{
		int start = 0;
		int link = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (check[i] == true && check[j] == true) start += input[i][j];
				if (check[i] == false && check[j] == false) link += input[i][j];
			}
		}

		ret = min(ret, abs(start - link));
	}

	for (int i = prev + 1; i < n; ++i)
	{
		check[i] = true;
		Combi(cnt + 1, i);
		check[i] = false;
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> input[i][j];

	Combi(0, 0);
	cout << ret << endl;

	return 0;
}