[Baekjoon] 14889번: 스타트와 링크

 

 

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

14889번: 스타트와 링크

 

---

 

문제 해결 과정

착안

총 $N$ 명의 인원을 $(N / 2)$ 명씩 두 팀으로 나누는 모든 방법에 대하여, 능력치 값을 계산해보고 능력치 차이의 최솟값을 구하고자 하였다. 이때 팀 이름에 관계 없이 점수 차이만 계산하면 되므로, 중복하여 계산할 필요 없이 가장 처음 번호의 인원(1번 사람)은 반드시 첫 번째 팀에 포함된다고 가정할 수 있다(예를 들면 1번 사람이 속한 팀을 무조건 스타트 팀이라고 가정하는 것과 같음).

 

한편, 첫 번째 팀에 $(N / 2)$ 명의 멤버가 배정되면 나머지 인원은 자동적으로 두 번째 팀에 속하므로 이를 활용하고자 하였고, 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 다른 경우의 $(N / 2)$ 명으로 팀이 구성되는 경우에 대해서도 모두 능력치 차이값을 계산하여 문제를 해결하고자 하였다.

 

구현

앞에서 언급한 것과 같이, 0번 인덱스를 1번 팀에 배정하고 이후는 순차적으로 $(N / 2)$ 명이 될 때까지 1번 팀으로 멤버를 배정하여 $(N / 2)$ 명이 되면 능력치 차이값을 계산한 다음 백트래킹을 통해 다른 경우에 대해서도 계산하였다.

 

다른 분의 코드를 참고하니 두 팀으로 나누는 방식을 더 간편하게 구한 것 같은데, 해당 코드의 원리가 아직 잘 이해되지 않아서 추가적으로 공부해봐야 할 것 같다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

int N;
int S[20][20];
int Min = 2147483647;

int TeamScore(vector<int>& team)
{
	int sum = 0;
	for (int i : team)
		for (int j : team)
			sum += S[i][j];

	return sum;
}

void Select(vector<int>& team, int n)
{
	if (n < N || !Min)
	{
		team.push_back(n);

		if ((int)team.size() == N / 2)
		{
			vector<int> team2;
			int idx = 0;
			for (int i = 0; i < N; i++)
			{
				if (team[idx] == i)
				{
					if (idx < N / 2 - 1)
						idx++;
					continue;
				}

				team2.push_back(i);
			}

			int diff = abs(TeamScore(team) - TeamScore(team2));
			if (Min > diff)
				Min = diff;

			return;
		}

		for (int i = n + 1; i < N; i++)
		{
			Select(team, i);
			team.pop_back();
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> S[i][j];

	vector<int> Team;
	Select(Team, 0);

	cout << Min << "\n";
	return 0;
}

 

실행 결과