[algorithm] 백준 - 스타트와 링크

이 문제는 재귀 문제이다.

 

사람을 스타트팀에 넣는 경우, 링크 팀에 넣는 경우로 재귀 함수를 구현한다.

스타트팀에 구성된 인원 수 : n/2
링크 팀에 구성된 인원 수: n/2
가 아닌 경우도 포함되겠지만, 

N(4 ≤ N ≤ 20, N은 짝수) 이므로 2초를 넘을 위험은 없다.

 

start.push_back(index);
permutation(index + 1);
start.pop_back();
link.push_back(index);
permutation(index + 1);
link.pop_back();

 

스타트팀과 링크팀에 구성된 인원 수가 n/2로 채워졌을 때,

능력치를 더하고, 가장 능력치 차가 나지 않는 경우의 수를 저장한다.

 

if(index == n){
        if(start.size() ==n / 2 && link.size() == n / 2){
        int sum = 0;
        for(int i = 0; i < start.size() - 1; i++){
            for(int j = i + 1; j < start.size(); j++){
                if(i == j) continue;
                sum += score[start[i]][start[j]] + score[start[j]][start[i]];
                sum -= score[link[i]][link[j]] + score[link[j]][link[i]];
            }
        }
        answer = min(answer, abs(sum));
        }
        return;
    }

 

코드는 이렇다.

//스타트와 링크
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int score[20][20];
int n;
int answer = 987654321;
vector<int> start;
vector<int> link;
void permutation(int index){
    if(index == n){
        if(start.size() ==n / 2 && link.size() == n / 2){
        int sum = 0;
        for(int i = 0; i < start.size() - 1; i++){
            for(int j = i + 1; j < start.size(); j++){
                if(i == j) continue;
                sum += score[start[i]][start[j]] + score[start[j]][start[i]];
                sum -= score[link[i]][link[j]] + score[link[j]][link[i]];
            }
        }
        answer = min(answer, abs(sum));
        }
        return;
    }
    start.push_back(index);
    permutation(index + 1);
    start.pop_back();
    link.push_back(index);
    permutation(index + 1);
    link.pop_back();
}
int main(void){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j =0; j < n; j++){
            cin >> score[i][j];
        }
    }
    permutation(0);
    cout << answer;
}