14889번 스타트와 링크

14889번: 스타트와 링크

전형적인 브루트포스 문제.

 

이전에 풀었던 N과 M문제를 참조하였다.

 

1. N명의 선수를 두 팀으로 나누기  : n C n/2

2. 각 팀을 2인1조로 구성하여 총 전력을 구하기 : n/2 C n

 

크게 두 분으로 나뉘어 있다.

 

막혔던 부분은 브루트포스 재귀문을 이용해 어떻게 두 팀을 동시에 구성할 것이냐에 관한 것이었다.

 

재귀를 돌릴 때마다 start팀과 link팀에 동시에 완전탐색을 통한 팀구성을 해야하나 싶었지만

 

두 팀은 배타적이기 때문에 한 팀의 정보만 저장해주면 다른 팀의 구성원도 동시에 결정되기 때문에

 

여느 브루트포스 문제와 다를 것이 없었다.

 

재귀조건을 if(!member[i])로만 설정하니 이전에 등장한 조합이 또 등장하여 시간초과로 터져버렸기 때문에 

 

N과M에서 사용한 기법을 참조하여 arr라는 배열을 추가하여 

 

중복된 조합을 걸러낼 수 있었다.

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

int N, cnt;
int map[21][21];
vector<int> start;
vector<int> link;
bool member[21];
int start_scr;
int link_scr;
vector<int> s_scr;
vector<int> l_scr;
vector<int> t_scr;
int arr[11];

void print_team() {//디버깅용
	cout << '\n';
	for (int i = 0; i < start.size(); i++) {
		cout << start[i] << " ";
	}
	cout << '\n';
	for (int i = 0; i < link.size(); i++) {
		cout << link[i] << " ";
	}
	cout << '\n';
}

void make_duo() {//팀 전력 구하기
	start_scr = link_scr = 0;
	for (int i = 0; i < start.size(); i++) {
		for (int j = 0; j < start.size(); j++) {
			if (i != j) {
				start_scr += map[start[i]][start[j]];
				start_scr += map[start[j]][start[i]];
			}
		}
	}

	for (int i = 0; i < link.size(); i++) {
		for (int j = 0; j < link.size(); j++) {
			if (i != j) {
				link_scr += map[link[i]][link[j]];
				link_scr += map[link[j]][link[i]];
			}
		}
	}

	s_scr.push_back(start_scr);
	l_scr.push_back(link_scr);
}

void make_team(int cnt) {//팀 구성
	if (cnt == N / 2) {
		start.clear();
		link.clear();
		for (int i = 0; i < N; i++) {
			if (member[i]) {
				start.push_back(i);
			}
			else {
				link.push_back(i);
			}
		}
		//for (int i = 0; i < 3; i++) { cout << arr[i] << " "; }
		//cout << '\n';
		make_duo();
		//print_team();
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!member[i] && arr[cnt-1] <= i) {
			arr[cnt]=i;
			member[i] = true;
			make_team(cnt + 1);
			member[i] = false;
		}
		else if(cnt==0) {
			arr[cnt] = i;
			member[i] = true;
			make_team(cnt + 1);
			member[i] = false;
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	make_team(0);

	for (int i = 0; i < s_scr.size(); i++) {
		int temp = abs(s_scr[i] - l_scr[i]);
		t_scr.push_back(temp);
	}
	sort(t_scr.begin(), t_scr.end());

	cout << t_scr.front()/2;
	return 0;
}