백준 알고리즘 14889_스타트와 링크 C++

문제

(링크)14889번: 스타트와 링크 (acmicpc.net)

14889번: 스타트와 링크

 

사고과정

정답률은 높은데 나는 어려웠다. 팀을 어떻게 나누느냐가 관건인데다 재귀를 사용하지 않고 풀려고 했더니, 어떤 방법으로 팀을 나눠야할지는 생각은 했는데 구현하기가 너무 귀찮을 것 같아서 그냥 재귀를 이용하기로 했다. 

제일 먼저 생각한 것은 팀1에 0번 선수를 고정해 놓는 것이다. 0번 선수를 기준으로 팀을 나눈다면 어쩄든 모든 경우의 수를 탐색할 수 있기 때문이다. 

다음은 어떤 방법으로 선수를 1번팀에 넣고 나머지 선수들을 2번팀에 넣을 것인가를 생각했다. vector를 사용해서 team1에 넣었다면 나머지 선수는 team2에 넣어야 하는데, team1을 기준으로 재귀적으로 탐색 시 team1 vector엔 선수들의 이름을 넣을 수 있지만 team2엔 넣기 어렵다. 그렇다고 team1의 크기와, 전체 분할 수를 같이 비교하자니 필요없는 부분까지 탐색할 것 같았고 종료조건이 지저분해 질 것 같아서 다른 방향으로 진행하기로 했다.

그래서 생각한 것이 모든 선수가 team2에 있다고 가정하고 team1에 선수들을 대려오는 것. 이 때, 각 vector엔 선수이름이 저장되는 것이 아니라, 선수이름의 index에 각 팀에 소속되어 있는가가 저장된다. 이후 팀원들의 시너지 합을 구한다. 

 

내코드

#include <iostream>
#include <vector>

using namespace std;


int getAbility(vector<int> team, int N, vector<vector<int>> synergy) {
	int sum = 0;
	vector<int> stack;
	for (int i = 0; i < N; i++) {
		if (team[i] == 1) {
			stack.push_back(i);
			//cout << i<<' ';
		}
	}
	//cout << endl;
	for (int i = 0; i < stack.size() - 1; i++) {
		for (int j = i + 1; j < stack.size(); j++) {
			int x = stack[i];
			int y = stack[j];
			sum += (synergy[x][y] + synergy[y][x]);
		}
	}
	//cout << "sum  " << sum << endl;
	return sum;
}


void makeTeam(int name,int size, int N,vector<int> team1,vector<int> team2, vector<vector<int>> synergy,vector<int>& difference) {
	team1[name] = 1;
	team2[name] = 0;
	if (size == N / 2) {
		int ability_1 = getAbility(team1, N, synergy);
		int ability_2 = getAbility(team2, N, synergy);

		int differ = ability_1 - ability_2;
		if (differ < 0)differ *= -1;
		//cout << "differ" << differ << endl<<endl;
		difference.push_back(differ);
		return;
	}

	for (int i = name + 1; i < N; i++) {
		makeTeam(i, size + 1, N, team1, team2, synergy, difference);
	}
}



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

	vector<int> team1(N,0);
	vector<int> team2(N, 1);
	vector<int> difference;
	makeTeam(0, 1, N, team1, team2, Synergy, difference);
	

	int min = difference[0];
	for (i = 1; i < difference.size(); i++) {
		if (min > difference[i])min = difference[i];
	}
	cout << min;

	return 0;
}

team1은 0으로 team2는 1로 초기화를 한다. 이후 팀원을 뽑는다. 최근에 들어온 선수를 기점으로 그 이후의 선수를 차례대로 team1으로 영입한다. 그러다 team1의 선수가 N/2명이 되면 두 팀간 전력차를 구하게 된다. team1, team2 vector에는 각 vector의 index에 해당하는 선수가 소속여부가 저장되어 있기 때문에 두 팀의 전력을 구할 때, 새로운 백터에 각 선수의 번호를 저장하고 서로의 전력을 더해준다. 

 

피드백

재귀함수를 이용한 풀이가 떠올랐으면 그대로 실행해 볼 것. 실제 테스트를 볼 땐 시간이 충분하지 않을 것이므로. 일단 문제를 빠르게 풀기라도 해야한다.

메모리도 많이 사용하고 시간복잡도도 높다. 2중반복문이 들어가서 그런 것 같은데 이 부분을 해결하기 위해 어떤 방법이 있는지 생각해 볼 것.