[백준] 14889번 스타트와 링크

14889번: 스타트와 링크

조합 문제의 변형이다.

N에 따라 나눌 수 있는 팀의 경우의 수를 살펴보면

 

N                   팀 

2                  1 | 2

====================

    4              1, 2 | 3, 4

                    1, 3 | 2, 4

                    1, 4 | 2, 3

====================

      6        1, 2, 3 | 4, 5, 6

                1, 2, 4 | 3, 5, 6

                1, 2, 5 | 3, 4, 6

                1, 2, 6 | 3, 4, 5

                1, 3, 4 | 2, 5, 6

                1, 3, 5 | 2, 4, 6

                1, 3, 6 | 2, 4, 5

                1, 4, 5 | 2, 3, 6

                1, 4, 6 | 2, 3, 5

                1, 5, 6 | 2, 3, 4

====================

...                    ...

 

이렇게 맨 첫 번째 값은 고정이고 나머지 값들이 오름차순으로 배열된다는 점에서

이런 수식이 나오게 된다.

 

백트래킹으로 팀을 나눠준 뒤 구성이 다 될 때마다 능력치를 계산해준 뒤

최솟값을 저장하여 출력한다

#include <iostream>
#include <algorithm>
using namespace std;
int S[20][20] = { 0 }, Min = 100000000;
int team[20] = { 0 }, team_start[10] = { 0 }, team_link[10] = { 0 };

void solution(int N, int current, int cnt) {
	if (cnt == N / 2 - 1) { //팀이 다 만들어졌을 경우 팀 분리 후 능력치 계산
		int start = 0, link = 0;
		for (int i = 0; i < N; i++) {
			if (team[i] == 1) { //스타트 팀
				team_start[start] = i;
				start++;
			}
			else { //링크 팀
				team_link[link] = i;
				link++;
			}
		}
		start = 0, link = 0;
		for (int i = 0; i < N / 2; i++) {
			for (int j = 0; j < N / 2; j++) {
				if (i != j) { //능력치 계산
					start += S[team_start[i]][team_start[j]];
					link += S[team_link[i]][team_link[j]];
				}
			}
		}
		Min = min(Min, abs(start - link));
	}
	else {
		for (int i = 1; i < N; i++) {
			if (current < i) {
				team[i] = 1;
				cnt++;
				solution(N, i, cnt);
				cnt--;
				team[i] = 0;
			}
		}
	}
}

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

	team[0] = 1;
	solution(N, 0, 0);

	cout << Min;
	return 0;
}