백준 14889 스타트와 링크

조건도 많지 않고, 문제도 간단하여 풀기 쉬운 문제였다.

재귀 함수를 이용하여 완전 탐색만 진행해 주면 되었다.

 

선수들을 배열로 놓고, idx를 증가시켜가며 추가하거나 추가하지 않는 경우의 수를 나누면 되었다.

추가한 선수들을 true로 두어서, cal함수에서 이중 for문을 돌며 true인 두 선수의 능력치를 더해주었다.

이어서 false인 두 선수의 능력치를 더하였다.

마지막으로 두 합의 차이를 ans vector에 저정한 후 min_element함수를 통해 출력하면 끝이난다.

 

코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<int> ans;
int n;
int s[20][20];
int check[20];
 
void cal() {
    int sum1 = 0, sum2 = 0;
    //팀에 들어 있는 사람들 능력치 더한다.
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (check[i] && check[j]) sum1 += s[i][j] + s[j][i];
        }
    }
    //팀에 넣지 않은 사람들 능력치 더한다.
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!check[i] && !check[j]) sum2 += s[i][j] + s[j][i];
        }
    }
    ans.push_back(abs(sum1 - sum2));
}
 
void solve(int idx, int cnt) {
    //반을 뽑았으면 능력치 계산
    if (cnt == n / 2) {
        cal();
        return;
    }
    //골라야 할 idx가 n을 초과하면 return
    if (idx == n)return;
 
    //팀에 해당 idx의 인원을 추가한다.
    check[idx] = true;
    solve(idx + 1, cnt + 1);
    //해당 idx의 인원을 추가하지 않고 넘어간다.
    check[idx] = false;
    solve(idx + 1, cnt);
}
 
int main(int argvc, char** argv) {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &s[i][j]);
        }
    }
 
    solve(0, 0);
 
    printf("%d\n", *min_element(ans.begin(), ans.end()));
 
    return 0;
}