[백준 14889번 - 스타트와 링크] C++ 풀이

백준 14889번.

총 n 명을 n/2 명씩 두 팀으로 나누고, 각 팀의 능력치 합을 구해서 차이를 최소로 하도록 하는 문제이다.

만약 각 팀에 3명씩 있고, 1,2,3번이 스타트팀, 3,4,5번이 링크팀이라면,

스타트팀 : S12 + S21 + S13 + S31 + S23 + S32

링크팀 : S34 + S43 + S35 + S53 + S45 + S54 가 된다.

사용한 알고리즘

- 백트래킹

 

순차적으로 탐색하면서 해당 맴버를 선택하거나/선택하지 않거나. 해서 함수를 호출하도록 했다.

depth 가 n / 2 이 되면 호출을 멈추도록 재귀를 구현하였다. 그리고 거기서 두 팀 멤버 능력치의 차를 구해서 기존거보다 더 작으면 갱신해주었다.

 

완성된 코드

#include <stdio.h>
#include <vector>
#include <stack>
#include <math.h>

using namespace std;

int n;
vector<vector<int>> v;

int ans = 1001;

void dfs(int x, vector<int> s, vector<bool> visited) {
	if (s.size() == n / 2) {
		int a1 = 0;
		int a2 = 0;
		for(int i = 0; i < s.size(); ++i) {
			for(int j = 0; j < s.size(); ++j) {
				if (s[i] != s[j]) {
					a1 += v[s[i]][s[j]];
				}
			}
		}
		vector<int> v2;
		for(int i = 0; i < n; ++i) {
			if (visited[i] == false) {
				v2.push_back(i);
			}
		}
		for(int i = 0; i < v2.size(); ++i) {
			for(int j = 0; j < v2.size(); ++j) {
				if (i != j) {
					a2 += v[v2[i]][v2[j]];
				}
			}
		}
		ans = (ans > abs(a1 - a2)) ? abs(a1 - a2) : ans;
		return;
	} else {
		for(int i = x; i < n; ++i) {
			s.push_back(i);
			visited[i] = true;
			dfs(i + 1, s, visited);
			visited[i] = false;
			s.pop_back();
		}
	}
}

int main() {
	scanf("%d", &n);
	vector<bool> visited;
	v.assign(n + 1, vector<int>(n + 1));
	visited.assign(n + 1, false);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			scanf("%d", &v[i][j]);
		}
	}
	vector<int> s;
	dfs(0, s, visited);
	printf("%d\n", ans);
}