백준 14889 / 스타트와 링크

순열을 이용한 브루트 포스 문제.

아이디어가 필요하다. 

n의 최대값이 20이기 떄문에 20명으로 구성된 순열에 대해 모든 값을 구하는 건 시간초과가 발생한다 (20!)

그렇다면 20명을 두 팀으로 나누는 아이디어가 필요.

해결법은 0(n/2개)과 1(n/2개)로 구성된 n짜리 배열을 만들고, 

첫번째 팀은 0 두번쨰 팀은 1로 배정받는 방식이다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
 
int arr[21][21];
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int n;
    
    cin >> n;
    int sum = 0;
    int mid = n / 2;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
 
            cin >> arr[i][j];
            sum += arr[i][j];
        }
    }
 
    vector<int>member;
    member.resize(n);
 
    for (int i = 0; i < mid; i++) {
        member[i] = 1;
    }//A팀
 
    sort(member.begin(), member.end());
 
    int ans = 2000000000;
 
    do {
        vector<int>one, two;
 
        for (int i = 0; i < n; i++) {
            if (member[i] == 0) {
                one.push_back(i);
            }
            if (member[i] == 1) {
                two.push_back(i);
            }
        }
 
        int onep = 0;
        int twop = 0;
 
        for (int i = 0; i < one.size(); i++) {
            int a = one[i];
 
            for (int j = 0; j < one.size(); j++) {
                if (a != one[j]) {
                    onep += arr[a][one[j]];
                }
            }
 
 
        }
 
        for (int i = 0; i < two.size(); i++) {
            int a = two[i];
 
            for (int j = 0; j < two.size(); j++) {
                if (a != two[j]) {
                    twop += arr[a][two[j]];
                }
            }
        }
 
        int diff;
        diff = abs(onep - twop);
 
        if (ans > diff) {
            ans = diff;
        }
 
 
 
    } while (next_permutation(member.begin(), member.end()));
 
 
    cout << ans;
}

재귀함수를 사용하여 팀을 나눌수도 있다.

코드 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
 
using namespace std;
 
int arr[21][21];
vector<int>member;
int n;
int small = 2000000000;
 
 
int split(int idx, int cnt, vector<int>&one) {
    if (idx >= n)return 0;
    if (cnt > n / 2)return 0;
    if (cnt == n / 2) {
        int tmp = 0;
        int tmp2 = 0;
 
        vector<int>two;
 
        for (int i = 0; i < n; i++) {
            bool can = false;
            for (int j = 0; j < one.size(); j++) {
                if (i == one[j])can = true;
            }
            if (can == false) {
                two.push_back(i);
            }
        }
 
        for (int i = 0; i < one.size(); i++) {
            for (int j = 0; j < one.size(); j++) {
                if (one[i] != one[j]) {
                    tmp += arr[one[i]][one[j]];
                }
            }
        }
 
        for (int i = 0; i < two.size(); i++) {
            for (int j = 0; j < two.size(); j++) {
                if (two[i] != two[j]) {
                    tmp2 += arr[two[i]][two[j]];
                }
            }
        }
 
        int ans = 0;
        ans = abs(tmp - tmp2);
 
        if (small > ans) {
            small = ans;
        }
 
        return 0;
    }
 
    one.push_back(member[idx]);
    split(idx + 1, cnt + 1, one);
    one.pop_back();
    split(idx + 1, cnt, one);
 
}
int main() {
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        member.push_back(i);
    }
 
    vector<int>one;
    vector<int>result;
 
    split(0, 0, one);
 
    cout << small;
}