[Brute Force - 조합] 스타트와 링크

 

예제 입력 1

4

0 1 2 3

4 0 5 6

7 1 0 2

3 4 5 0

예제 출력 1

0

예제 입력 2

6

0 1 2 3 4 5

1 0 2 3 4 5

1 2 0 3 4 5

1 2 3 0 4 5

1 2 3 4 0 5

1 2 3 4 5 0

예제 출력 2

2

예제 입력 3

8

0 5 4 5 4 5 4 5

4 0 5 1 2 3 4 5

9 8 0 1 2 3 1 2

9 9 9 0 9 9 9 9

1 1 1 1 0 1 1 1

8 7 6 5 4 0 3 2

9 1 9 1 9 1 0 9

6 5 4 3 2 1 9 0

예제 출력 3

1

 

 

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

 

 

- 절반은 1번팀, 나머지 절반은 2번팀이므로 순열로 풀 수 있다. {1,1,1,1,..., 2,2,2,2,....} 

그러나 N이 최대 20이므로 next_permutation을 STL없이 직접 구현할 경우 시간 복잡도가 20!이라 시간초과가 발생할 것 같아서 어차피 N/2만 "선택"해서 풀어야 하는 문제이므로 재귀로 조합을 구해서 풀었다.

#include <stdio.h>
#include <limits>

#define MIN(a,b) ((a)<(b)?(a):(b))

#define MAX_VALUE (2147483647)
#define MAX_COUNT (20)

int N;
int players[MAX_COUNT][MAX_COUNT] = { 0, };
bool used[MAX_COUNT];

int minResult = MAX_VALUE;

int abs(int x)
{
	return x < 0 ? -x : x;
}

class Vector
{
public:
	int items[10];
	int size;

	Vector()
	{
		size = 0;
	}

	void Add(int item)
	{
		items[size] = item;
		size++;
	}
};

void go(int(*data)[MAX_COUNT], int start, int cnt)
{
	if (cnt == N / 2)
	{
		Vector first;
		Vector second;

		int firstResult = 0;
		int secondResult = 0;

		for (int i = 0; i < N; i++)
		{
			if (used[i]) // 선수 i가 1팀
			{
				first.Add(i);
			}
			else // 2팀	
			{
				second.Add(i);
			}
			
		}

		// first
		for (int i = 0; i < first.size; i++)
			for (int j = i + 1; j < first.size; j++)
			{
				firstResult += players[first.items[i]][first.items[j]];
				firstResult += players[first.items[j]][first.items[i]];
			}
				

		// second
		for (int i = 0; i < second.size; i++)
			for (int j = i + 1; j < second.size; j++)
			{
				secondResult += players[second.items[i]][second.items[j]];
				secondResult += players[second.items[j]][second.items[i]];
			}

		minResult = MIN(minResult, abs(firstResult - secondResult));

		return;
	}

	for (int i = start; i < N; i++)
	{
		used[i] = true;
		go(data, i + 1, cnt + 1);
		used[i] = false;
	}
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &players[i][j]);
		}
	}

	go(players, 0, 0);

	printf("%d\n", minResult);

	return 0;
}