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

문제 링크

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

 

 

코드 구현

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> Stats;
int minValue = 100;
bool selected[20];

int Diff()
{
	int diff;
	int S = 0, L = 0;

	// selected 에서 true 면 스타트 팀, false 면 링크 팀
	for (int i = 0; i < Stats.size(); i++)
	{
		for (int j = 0; j < Stats.size(); j++)
		{
			if (i == j) continue;

			if (selected[i])
			{
				if (selected[j]) S += Stats[i][j];
			}
			else
			{
				if (!selected[j]) L += Stats[i][j];
			}
		}
		
	}

	diff = S - L;

	diff = (diff > 0) ? diff : -diff;

	return diff;
}

// idx : 현재 팀원, count : 팀원 수
void Backtrack(int idx, int count)
{
	// 팀원 수는 전체 인원의 절반
	if (count == Stats.size() / 2)
	{
		// 팀이 만들어졌으므로 차이 값 계산
		int diff = Diff();
		minValue = min(minValue, diff);
		return;
	}

	// 스타트 팀을 true로 체크
	for (int i = idx; i < Stats.size(); i++)
	{
		selected[i] = true;
		Backtrack(i + 1, count + 1);
		// 계산 후 기존의 true 값을 다시 false로
		selected[i] = false;
	}
}

int main()
{
	int N, S;

	cin >> N;
	Stats.resize(N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> S;
			Stats[i].push_back(S);
		}
	}
	
	Backtrack(0, 0);

	cout << minValue;

	return 0;
}

 

 

해결 방법

재귀 함수를 이용한 백트래킹으로 N/2 명인 두 팀을 구성하였다. 팀이 만들어지면 바로 두 팀의 능력치 차이를 계산하고 minValue 값에 넣어준다. 팀이 만들어지는 모든 경우에서 능력치 차이가 가장 작은 값을 도출하게 하였다. 

두 팀을 나누는 경우의 수를 찾는 것이 관건이라 할 수 있을 것 같다.