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

문제
스타트링크에 다니는 사람들이 모여서 축구를 한다. 모인 사람은 항상 짝수인 N명이 모였으며 스타트팀과 링크팀으로 나누려고 한다.
이때 i와 j가 팀이 되었을 때 능력치가 있는데 N명이 두 팀으로 나눴을 때 각각 팀의 능력치를 구하여 두 팀의 능력치 차이가 최소가 되도록 구하라.

입력
첫째 줄에 N이 주어진다.
둘째 줄부터 N개의 줄에 N개의 능력치가 주어진다.
i번째 줄의 j번째 수는 i와 j가 팀이 되었을 때 능력치이다.

출력
스타트팀과 링크 팀의 능력치의 차이가 최소가 되는 값을 출력한다.

---

접근

먼저 두 개의 팀으로 나눴다. 스타트팀은 1, 링크팀은 0으로 표시를 한다.

이후 능력치를 조사하는데 2차원 배열을 탐색할 때 행과 열의 인덱스가 모두 1일 때는 스타트 능력치에 더하고 모두 0일 때는 링크 능력치에 더하여 차이의 최솟값을 찾는다.

 

구현

solve()에서 먼저 두 개의 팀으로 나누도록 한다. team배열이 0이라면 1로 표시를 하고 picked를 증가시켜 재귀호출을 한다.

이후 picked가 N의 반이라면 각 팀의 능력치를 구하고 두 팀의 능력치 차이를 구하여 최종해를 위한 비교를 한다.

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
#include<cmath>
using namespace std;

int N;
int answer = 1001;
int team[20];
int stats[20][20];

void solve(int next, int picked) {
	if (picked == (N / 2)) {
		int start_stat = 0;
		int link_stat = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (team[i] == 1 && team[j] == 1) {
					start_stat += stats[i][j];
				}
				else if (team[i] == 0 && team[j] == 0) {
					link_stat += stats[i][j];
				}
			}
		}
		answer = min(answer, abs(start_stat - link_stat));
		
	}
	for (int i = next; i < N; i++) {
		if (!team[i]) {
			team[i] = 1;
			solve(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];
		}
	}

	solve(0, 0);
	cout << answer << endl;
	
}