[백준OJ] 14889번 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

 

-풀이-

백트래킹을 이용하여 모든 경우에서의 start팀과 link 팀 차이의 최솟값을 구해줬다.

dfs로 전체 경우의수를 탐색한 다음, 팀 구성이 완료되면, 각 경우마다 for문을 이용하여 start팀의 멤버면, 해당 멤버와 start팀의 모든 멤버와의 시너지를 모두 더해주고, link팀이면 해당 멤버와 모든 link팀의 시너지 점수를 모두 더해준뒤, 두 팀사이의 차이를 abs를 이용하여 절댓값을 씌워주어 갱신시켰다.

 

-시간복잡도-

팀을 구하는 경우의수는 nCn/2 가 걸리고, 팀이 선정이 됐을때, 이중for문을 돌리므로 n*n의 시간이 걸린다.

따라서 총 시간복잡도는 O(nCn/2 * n*n) 이 되지만, N의 값이 20이하이므로, 충분히 시간안에 들어간다.

 

-코드-

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int maze[20][20];
int n, result = 987654321;
bool start_m[20] = { 0 };
int cnt = 0;

void check(int n) {
	int start_sum = 0;
	int link_sum = 0;

	for (int i = 0; i < n; i++) {
		if (start_m[i]) {
			for (int j = 0; j < n; j++) {
				if (start_m[j]) {
					start_sum += maze[i][j];
				}
			}
		}
		else {
			for (int j = 0; j < n; j++) {
				if (!start_m[j]) {
					link_sum += maze[i][j];
				}
			}
		}
	}
	result = min(result, abs(start_sum - link_sum));
}

void dfs(int ind,int n) {
	if (cnt == n / 2) {
		check(n);
		return;
	}
	for (int i = ind + 1; i < n; i++) {
		start_m[i] = true;
		cnt++;
		dfs(i,n);
		start_m[i] = false;
		cnt--;
	}
}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
		}
	}
	dfs(-1,n);
	cout << result << "\n";
}