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

문제

백준 14889 문제 보기

접근 방법

학생들을 각각 a와 b팀으로 나눈다고 가정하고 벡터를 활용해 문제를 푼다. 모든 학생들의 a 또는 b팀으로 배정이 완료되면 a와 b팀의 인원이 같은 경우만 서로의 능력치를 합해 최소값을 구한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int N;
int s[21][21];
vector<int> a;
vector<int> b;
int ans = 123456789;

int dfs(int idx) {
    if(idx >= N) {
        if(a.size() == b.size()) {
            int aSum = 0;
            int bSum = 0;

            for(int i = 0; i < a.size(); i ++) {
                for(int j = i + 1; j < a.size(); j ++) {
                    aSum += s[a[i]][a[j]] + s[a[j]][a[i]];
                }
            }
            for(int i = 0; i < b.size(); i ++) {
                for(int j = i + 1; j < b.size(); j ++) {

                    bSum += s[b[i]][b[j]] + s[b[j]][b[i]];
                }
            }

            ans = min(ans, abs(aSum-bSum));
        }
        return 0;
    }

    // a로 배정
    a.push_back(idx);
    dfs(idx + 1);
    a.pop_back();

    // b로 배정
    b.push_back(idx);
    dfs(idx + 1);
    b.pop_back();
    return 0;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> s[i][j];
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}