백준 14889번 문제 ( 스타트와 링크 )

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

14889번: 스타트와 링크

이 문제는 팀을 반으로 나누어서 두 팀의 능력치를 최소화한 수치를 찾는 문제이다.

그래서 저는 브루트 포스를 이용하여 방문 배열을 이용함으로써

모든 경우를 탐색해서 모든 팀을 구성한 후 최솟값을 찾았다.

아래는 해당 문제를 해결한 소스이다. 

#include<stdio.h>
#include<algorithm>
#pragma warning(disable:4996)
int arr[21][21];
int visit[21];
int result = 9999999999;
void find_min(int start, int count,int N)
{
    if (count == N / 2)
    {
        int A = 0;
        int B = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (visit[i] == 1 && visit[j] == 1)
                    A = A + arr[i][j];
                else if (visit[i] == 0 && visit[j] == 0)
                    B = B + arr[i][j];
            }
        }
        int value = abs(A - B);
        if (value < result)
            result = value;
        return;
    }
    for (int i = start; i < N; i++)
    {
        visit[i] = 1;
        find_min(i + 1, count + 1, N);
        visit[i] = 0;
    }
}
int main()
{
    int min = 0;
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            scanf("%d", &arr[i][j]);
    }
    find_min(0,0,N);
    printf("%d", result);
}