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

문제
짝수인 N명의 사람들이 팀을 두 개로 나누어 축구를 한다.
이때 i와 j가 한 팀일 때의 능력치를 나타내는 표가 있을 때 양 팀의 능력치 합에 대한 차이를 최소로 했을 때의 값을 출력하라

입력
첫째 줄에 N(짝수, 4이상 20이하)
둘째 줄부터 N개의 줄에 능력치를 입력한다.

출력
능력치 차이의 최솟값을 출력

---

두 팀으로 나누는 방법을 먼저 생각해봐야 한다.

사람들은 고유의 등번호를 갖고있으므로 각 번호에 팀 번호를 부착하여 팀을 나누도록 한다.

team이라는 배열을 선언하여 각 번호에 해당하는 사람이 어느 팀인지 구분하도록 한다.

 

사람의 수만큼 for문을 돌아 백트래킹으로 팀을 나누고 팀을 다 나누었다면 각 팀의 능력치를 구하도록 한다.

능력치를 구하는 것은 어렵지 않다. 만약 해당 인덱스들이 1번이면 team1에 해당 좌표에 있는 능력치를 더한다. 이런식으로 각 팀의 능력치 합을 구한다음 두 팀의 능력치 차이를 비교하여 최솟값을 출력하도록 한다.

 

이 문제는 팀을 나누는 것과 각 팀의 능력치를 구하는 것을 구현하면 된다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

int N;
int stats[20][20];
int result=1000000000;
int team[20];


void solve() {
	int team1 = 0;
	int team2 = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
        	// 두 개의 인덱스가 모두 1번팀이라면
			if (team[i] == 1 && team[j] == 1) {
				team1 += stats[i][j];
			}
            // 두개의 인덱스가 모두 0번 팀이라면
			else if (team[i] == 0 && team[j] == 0) {
				team2 += stats[i][j];
			}
		}
	}
	
    // 두 팀의 총 능력치를 비교하여 최솟값을 구한다.
	int diff = abs(team1 - team2);
	result = min(result, diff);

	return;
}
void SetTeam(int next, int picked) {
	if (picked == N / 2) {
		solve();
		return;
	}
	
    // 팀 나누기 0번팀과 1번팀
	for (int i = next; i < N; i++) {
		if (team[i] == 0) {
			team[i] = 1;
			SetTeam(i+1, picked + 1);
			team[i] = 0;
		}
	}
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> stats[i][j];
		}
	}

	SetTeam(0, 0);
	cout << result << endl;
	return 0;
}