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

1. 문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

2. 풀이과정 

1. n명의 사람을 두 팀으로 나눈다

2. 각 팀의 능력치의 합을 계산한 후 차이를 구한다. 

3. 차이의 최솟값을 갱신한다.

1~3을 반복하며 스타트와 링크 팀의 능력치의 차이의 최솟값을 구할 수 있다. 

[코드설명]

stats[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.

 

dfs함수는 0번~n-1번 사람들 중 n/2명의 가능한 조합을 구해준다.

예를 들어 n = 4일 때, 0번 1번 2번 3번 사람이 있다고 가정하자.

이때 dfs함수는

0 1

0 2

0 3

1 2

1 3

2 3

을 생성한다. 

 

getDiff함수는 생성한 n/2명(ex: 0번 1번) 을 start팀, 나머지(ex: 2번 3번)를 link팀으로 설정한 후,

각 팀의 능력치의 합을 계산한 후 두 팀의 차이를 반환해준다.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;
int n;
vector<vector<int>> stats;
int min_diff = INT_MAX;

int getDiff(vector<int>& v) {
    int start_sum = 0, link_sum = 0;
    vector<int> start = v;
    vector<int> link;
    for(int i=0; i<n; i++) {
        if(find(start.begin(), start.end(), i)==start.end()) link.push_back(i);
    }
    for(int i=0; i<n/2; i++) {
        for(int j=i+1; j<n/2; j++) {
            start_sum += (stats[start[i]][start[j]]+stats[start[j]][start[i]]); 
            link_sum += (stats[link[i]][link[j]]+stats[link[j]][link[i]]);
        }    
    }
    return abs(start_sum - link_sum);
}

void dfs(vector<int>& v, int depth) {
    if(depth == n/2) {
        min_diff = min(min_diff, getDiff(v));
        return ;
    }
    int start = -1;
    if(!v.empty()) start = v.back();
    for(int i=start+1; i<n; i++) {
            v.push_back(i);
            dfs(v, depth+1);
            v.pop_back();
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    stats.resize(n);
    for(int i=0; i<n; i++) {
        stats[i].resize(n);
        for(int j=0; j<n; j++) cin >> stats[i][j];
    }
    vector<int> v;
    dfs(v, 0);
    cout << min_diff;
    return 0;
}