백준 15661번 : 링크와 스타트

문제링크 :https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 문제설명 

 

1. 선수들이 있는데 팀을 나눠야한다 .

2. 각선수들은 특정 선수와 팀을 할때 마다 능력치가 바뀐다.

3. 각 팀  능력치 차이를 최소로 될 수있게 팀을 꾸리고 최소 능력치 차이를 출력.

 

 알고리즘 

 

1. 조합 알고리즘을 이용하여 완전 탐색을 진행한다.

2. 재귀 함수 안에는 각 팀의 능력치를 더하는 연산을 진행하여 각 팀능력치 차를 계속 줄여 나간다.

 

 코드 

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
 
int N;
int arr[25][25];
int check[25];
int team1 = 0, team2 = 0;
int result = 2000000;
void func(int n, int cnt, int idx) {
    if (n == cnt) {
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j)continue;
                if (check[i] && check[j]) {
                    team1 += arr[i][j];
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j)continue;
                if (!check[i] && !check[j]) {
                    team2 += arr[i][j];
                }
            }
        }
 
        result = min(result, abs(team1 - team2));
        team1 = 0, team2 = 0;
        return;
    }
 
 
    for (int i = idx; i <= N; i++) {
        if (check[i]) continue;
        else {
            check[i] = 1;
            func(n, cnt + 1, i);
            check[i] = 0;
        }
    }
 
 
 
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i <= N; i++)check[i] = 0;
 
    //팀원수 1 부터 N/2 까지 
    for (int i = 1; i <= N / 2; i++) {
        func(i, 0, 1);
        for (int j = 0; j <= N; j++)check[j] = 0;
    }
    cout << result;
 
}