BOJ 14889 스타트와 링크

문제출처 : https://www.acmicpc.net/problem/14889

1. 문제요약

- 총 N명의 사람을 N/2 명씩 팀을 나눔

- 사람 번호를 1, 2, 3, 4라 했을때, 팀 1은 1, 2 / 팀 2는 3, 4

- 팀 능력치는 s[1][2] + s[2][1] 

                  s[3][4] + s[4][2] 이다.(s[1][2], s[2][1]은 서로 다를 수 있다.)

- 팀 능력치 차이가 최소값은?

- 4 <= N <= 20 (N은 짝수)

2. 접근방법

- 한명의 사람이 스타트팀인지 링크 팀인지 구분

- 2^N

3. 시간복잡도

- 2^N

4. 회고

- 난 팀 능력치 계산을 팀을 만들 때 마다 하게 했는데...(사실 재귀를 거치면서 합산하면 된다고 생각은 했지만, 구현을 못했음)

- 그냥 for문으로 선택된 팀원이 i 이미 팀은 팀원을 1, 2 라 하면 sum += s[i][j] + s[j][i]; 하면 되는데...

- 스타트팀 : 1, 2 / 링크팀 : 3, 4 인 경우와

  스타트팀 : 3, 4 / 링크팀 : 1, 2 인 경우는 팀 능력치 차이가 같다.

- 난 이걸 해결 못해서 그냥 모든 경우(2^N)으로 해결했다.

- 해결하는 가장 쉬운 방법은 그냥 1을 한팀에 고정시키면 된다.

- next_permutation으로 4명이면 0 0 1 1을 순열로 만들어서 0 인경우 A팀 1 인경우 B팀으로 구분시키는 방법도 있음

- 사람을 순열돌리는 것보다 시간이 빠르며 최악 20! / 10! * 10! = 190,000

소스코드

#include<iostream>
using namespace std;

int n, s[21][21], teamA[21], teamB[21], ans = 987654321;

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

int calScore(int team[21]){
	int temp = 0;
	for (int i = 0; i < n / 2 - 1; i++){
		for (int j = i + 1; j < n / 2; j++){
			temp += s[team[i]][team[j]] + s[team[j]][team[i]];
		}
	}
	return temp;
}

void dfs(int num, int cnt_a, int cnt_b){
	if (cnt_a == n / 2 && cnt_b == n / 2){
		int score_a = calScore(teamA);
		int score_b = calScore(teamB);
		if (abs(score_a - score_b) < ans)
			ans = abs(score_a - score_b);
		return;
	}

	// teamA
	if (cnt_a < n / 2){
		teamA[cnt_a] = num;
		dfs(num + 1, cnt_a + 1, cnt_b);
	}
	// teamB
	if (cnt_b < n / 2){
		teamB[cnt_b] = num;
		dfs(num + 1, cnt_a, cnt_b + 1);
	}
}

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> s[i][j];

	dfs(1, 0, 0);
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]